题目描述

blablabla

样例

//差一个
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e8+10;
typedef long long pll;
bool st[N];
bool check(int x)
{
     string s1 = to_string(x);
     bool flag = true;
     for(int i=0,j=s1.size()-1;i<j;i++,j--){
        if(s1[i]!=s1[j]) return false;
     }
     return true;
}
int main()
{
    for(int i=2;i*i<1e7;i++){
        if(!st[i]){
            for(int j=i*i;j<1e7;j+=i){
                st[j] = true;
            }
        }
    }
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
       if(!st[i] && check(i)) cout<<i<<"\n";
    }
    return 0;
}
//看完之后知道
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
#define endl '\n'
int a, b;
const int N = 100000010;
int primes[N];
int st[N];
int cnt;

//线性筛
void get_primes(int n){
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;

        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}


//双指针判断回文
bool is_huiwen(int n)
{
    if(n<10) return true;

    string s=to_string(n);

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

signed main(){
    cin >> a >> b;
    //偶数位回文数 奇数位之和 = 偶数位之和 即能被11整除
    //所以一定不是质数
    //所以可以缩小范围到1e7以内 然后线性筛素数
    if(b >= 1e7){ 
        b = 1e7;
    } 

    get_primes(b);

    for(int i=0;i<=cnt;i++){
        if(primes[i]>=a  && is_huiwen(primes[i])) cout<<primes[i]<<endl;
    }

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla