题解

这道题直接暴力模拟，对于每一个数判断一遍质数和回文数。分析一下复杂度，计算质数（直接法）是 $O(n)$ 的，而回文数也是 $O(log_{10} n)$ 的，一共判断 $n$ 个数，复杂度 $O(n^2)$，完全可以接受。

int main()
{
    scanf("%d", &n);
    for (int i = 11; i <= n; i++)
    {
        if (prime(i) && moslem(i)) // prime质数 moslem回文数
            cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

程序的框架很简单，接下来看 $prime$ 和 $moslem$ 的实现了。质数判断应该都会，不用筛法，直接枚举可能的因数：

bool prime(int n)
{
    for (int i = 2; i <= n - 1; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}

当然如果用筛法会更快，毕竟这是连续的 $n$ 个数，如果用上预处理 $O(n)$ 查询 $O(1)$ 的欧拉筛，那不就起飞了……

其实没有必要，这边的回文数判断实现已经定好必须 $O(log_{10} n)$，因为必须访问到每一个数位。注意了，这里说到数位了，这是我们其实转换成字符串更快：

string s = "";
while (n > 0)
{
    s = char(n % 10 + '0') + s;
    n /= 10;
}

这段代码会把大于 $0$ 的数字 $n$ 转化成字符串 $s$，这里说是最少 $11$，那必然可以使用。

然后来一套类双指针，一前一后往中间扫描：

for (int i = 0, j = s.length() - 1; i <= j; i++, j--)
{
    if (s[i] != s[j]) return false;
}
return true;

$AC$ $Code$

#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0;
bool prime(int n)
{
    for (int i = 2; i <= n - 1; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
bool moslem(int n)
{
    string s = "";
    while (n > 0)
    {
        s = char(n % 10 + '0') + s;
        n /= 10;
    }

    for (int i = 0, j = s.length() - 1; i <= j; i++, j--)
    {
        if (s[i] != s[j]) return false;
    }
    return true;
}
int main()
{
    scanf("%d", &n);
    for (int i = 11; i <= n; i++)
    {
        if (prime(i) && moslem(i))
            cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

这题可以借鉴一下我在二星题单里讲过的一道题

正文

1. 判断素数的函数：通过循环 2 ~ x - 1 是否能被整除而判断是否为素数，是则返回 true，否则返回false

#include
using namespace std;
bool sushu(int x)
{
    if (x % 2 == 0) return false;
    if (x % 5 == 0) return false;
    for (int i = 2; i <= x - 1; i++)
        if (x % i == 0) return false;
    return true;
}

2. 判断回文的函数：把数字 n1 通过模10得到其所有位数，依次倒着存储进整数变量 sum，判断两者是否相等，相等说明是回文，返回true，否则返回false

bool huiwen(int n1)
{
    int n2 = n1, sum = 0;
    while (n1 > 0)
    {
        sum = sum * 10 + n1 % 10;
        n1 /= 10;
    }
    if (sum == n2) return true;
    else return false;
}

AC Code

#include
using namespace std;
bool sushu(int x)
{
    if (x % 2 == 0) return false;
    if (x % 5 == 0) return false;
    for (int i = 2; i <= x - 1; i++)
        if (x % i == 0) return false;
    return true;
}
bool huiwen(int n1)
{
    int n2 = n1, sum = 0;
    while (n1 > 0)
    {
        sum = sum * 10 + n1 % 10;
        n1 /= 10;
    }
    if (sum == n2) return true;
    else return false;
}

int main()
{
    int n, num = 0;
    cin >> n;
    for (int i = 11; i <= n; i++)
    {
        if (sushu(i) && huiwen(i))
            num += 1;
    }
    cout << num << endl;
    return 0;
}

某位蒟蒻的题解 这道题除了废手，还真没啥 本人注重格式化

#include<iostream>
using namespace std;
int z(int a){//质数~~
    int sum=0;
    for(int i=2;i<a;i++){
        if(a%i==0){
            sum++;
            break;
        }
    }
    if(sum!=0){
        return false;
    }
    return true;
}
int h(int b){//回文数~~
    int n1=b,sum=0;
    while(b!=0){
        sum=sum*10+b%10;
        b/=10;
    }
    if(sum==n1){
        return true;
    }
    return false;
}
int main(){
    int n,sum=0;
    cin>>n;
    for(int i=11;i<=n;i++){
        if(z(i) && h(i)){
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

这题写两个函数，一个判断是否为质数，一个判断是否为回文数

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,sum;
bool check(int n) //判断质数
{
    for(int i = 2;i<n;i++)
    {
        if(n%i == 0)
        {
            return 0;
        }
    }
    return 1;
}
bool huiwenshu(int x) //判断回文数
{
    int a[100],k = 0,s = 0,num = x;
    while (x >= 1)
    {
        a[k] = x%10;
        x/=10;
        k+=1;
    }
    for (int i = 0;i<k;i++)
    {
        s += a[i]*pow(10,k-i-1);
    }
    return s == num;
}
int main()
{
    cin >> n;
    for(int i = 11;i<=n;i++)
    {
        if(check(i) == true)
        {
            if(huiwenshu(i) == true)
            {
                sum++; //都符合条件+1
            }
        }
    }
    cout << sum;
}

先用埃氏筛法筛出质数，再判断是否为回文数

C++代码

//埃氏筛法
for (int i = 2; i <= n; i++)
{
    if (!isnp[i])
    {
        m++;
        prime[m] = i;
        for (int j = 2 * i; j <= n; j += i)
        {
            isnp[j] = true;
        }
    }
}

//检验是否为回文数
bool check(int num)
{
    int a[10], k = 0, s = 0, x = num;
    while (x >= 1)
    {
        a[k] = x % 10;
        x /= 10;
        k++;
    }
    for (int i = 0; i < k; i++)
    {
        s += a[i] * pow(10, k - i - 1);
    }
    return s == num;
}

Python代码

#埃氏筛法
for i in range(2, n + 1):
    if not isnp[i]:
        prime.append(i)
        for j in range(i * 2, n + 1, i):
            isnp[j] = 1

#判断是否为回文数
cnt = 0
for p in prime:
    if p >= 11:
        s = str(p)
        if s[::-1] == s: #s倒着和正着是否一样
            cnt += 1

#include<bits/stdc++.h>
using namespace std;
short n,sum;
int main(){
    cin>>n;
    for(short i=11;i<=n;i++){ // 从11开始枚举
        bool flag=true; // 第一层循环中flag的含义为是否为素数
        for(short j=2;j<i;j++){
            if(i%j==0)flag=false; // 如果除了1和本身外有因数，则不是素数
        }
        if(flag){
            short x=i;
            string str=""; // 把数字转为字符串
            while(x>0){
                char c=(x%10)+'0';
                str=c+str; // 从右往左转换
                x/=10;
            }
            short sizee=str.size();
            for(short j=0;j<sizee;j++){
                if(str[j]!=str[sizee-j-1])flag=false; // 判断回文
            }
            if(flag)++sum; // 第二层循环中flag的含义为是否为回文数
        }
    }
    cout<<sum;
    return 0;
}

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

bool is_prime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

bool is_palindrome(int num) {
    std::string num_str = std::to_string(num);
    std::string reversed_num_str = num_str;
    std::reverse(reversed_num_str.begin(), reversed_num_str.end());
    return num_str == reversed_num_str;
}

int main() {
    int n;
    std::cin >> n;
    
    int count = 0;
    for (int i = 11; i <= n; i++) {
        if (is_prime(i) && is_palindrome(i)) {
            count++;
        }
    }

    std::cout << count << std::endl;

    return 0;
}

函数解法解析：

1. is_prime(int num) 函数：用于判断一个整数是否为素数。素数是大于1且只能被1和自身整除的数。该函数通过遍历2到sqrt(num)的数，判断num能否被这些数整除来确定是否为素数。
2. is_palindrome(int num) 函数：用于判断一个整数是否为回文数。回文数是指从左向右和从右向左读都相同的数。该函数将整数转换为字符串，然后通过比较字符串和其反转后的字符串是否相等来判断是否为回文数。
3. main() 函数：在主函数中，首先读取用户输入的整数n，然后遍历从11到n的每一个整数，对于每个整数，判断是否同时为素数和回文数，如果是则计数器加一。最后输出符合条件的整数个数。
4. 绝对AC，放心食用

#include <bits/stdc++.h>
using namespace std;
int n,sum;
bool a1(int x)//判断质数
{
    for (int i=2;i<x;i++) if (x%i==0) return false;
    return true;
}
bool a2(int x)//判断回文数
{
    int a[10],k=0,s=0,n=x;
    while (n>=1) a[k]=n%10,n/=10,k++;
    for (int i=0;i<k;i++) s+=a[i]*pow(10,k-i-1);
    return s==x;
}
int main()
{
    cin>>n;
    for (int i=11;i<=n;i++) if (a1(i)&&a2(i)) sum++;
    cout<<sum;
    return 0;
}

#include <bits/stdc++.h> //万能头我最爱用
using namespace std;
int n, cnt = 0;
int prime(int n)
{
    for (int i = 2; i <= n - 1; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
int  moslem(int n)
{
    string s = "";
    while (n > 0)
    {
        s = char(n % 10 + '0') + s;
        n /= 10;
    }

    for (int i = 0, j = s.length() - 1; i <= j; i++, j--)
    {
        if (s[i] != s[j]) return false;
    }
    return true;
}
int main()//总体来说没有什么好说的
{
    scanf("%d", &n);
    for (int i = 11; i <= n; i++)
    {
        if (prime(i) && moslem(i))
            cnt++;
    }
    printf("%d\n", cnt);//回文数指左右对称的数
    return 0;
}