TLE大佬求调

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

prg_equal_depressed @ 2023-10-02 22:06:56

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int n,m;
bool f[100000005];
void run(int m){
    memset(f,1,sizeof(f));
    for (int i=2;i<=sqrt(m);i++){
        if (f[i]){
            for (int j=2;j<=m/i;j++) f[i*j]=false;
        }
    }
}
bool palindromes(int x){
    int s=0,k=x;
    while (x!=0){
        s=s*10+(x%10);x/=10;
    }
    return s==k?1:0;
}
int main(){
    cin>>n>>m;run(m);
    if (n%2==0) n+=1;
    for (int i=n;i<=m;i+=2){
        if (f[i]&&palindromes(i)){
            cout<<i<<endl;
        }
    }
    return 0;
}

最后一个点TLE,大佬求助Orz


by jrzhr @ 2023-10-02 22:22:29

提示 1: 找出所有的回文数再判断它们是不是质数(素数). @prg_equal_depressed


by prg_equal_depressed @ 2023-10-02 22:28:20

这是埃氏筛法啊,@fu_jian_ding_yi


by ruanwentao666 @ 2023-10-17 19:03:14

可以枚举一个数对称中心左边的数,从而算出对称中心右边的数,再判断是否是质数


by prg_equal_depressed @ 2023-10-27 18:15:10

@ruanwentao666 谢谢


|