88分,玄关。大佬求助!!!

P1217 [USACO1.5] 回文质数 Prime Palindromes

chenbingjie @ 2024-04-14 21:12:47

#include<bits/stdc++.h>
using namespace std;
bool pri[100000010];
void prime(int d){//埃筛
    memset(pri,true,sizeof(pri));
    pri[1]=false;
    int n=sqrt(d);
    for(int i=2;i<=n;i++){
        if(pri[i]){
            for(int j=2;j<=d/i;j++)pri[i*j]=false;
        }
    }
}
bool check_hui(int d){//回文
    string h=to_string(d);//c++11里把数字直接转成字符串
    string t=h;
    reverse(t.begin(),t.end());
    if(t==h)return true;
    else return false;
}
int main() {
    int a,b;
    cin>>a>>b;
    prime(b);
    if(a%2==0)a++;
    for(int i=a;i<=b;i+=2){
        if(i==9989899+1)break;
        if(pri[i]&&check_hui(i))cout<<i<<endl;
    }
    return 0;
}

by Weekoder @ 2024-04-14 21:38:49

@chenbingjie 卡常卡了半天没过去,你还是用 O(n) 的线性筛罢。


|