C++ 第九题TLE,请问该怎么优化(应用了欧拉筛)

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

花Q渔夫 @ 2022-11-19 17:45:29


#include<iostream>
#include<cmath> 
#include<cstring>
using namespace std;

int main(){
    int x,y;
    cin>>x>>y;
    bool a[y+1]={};
    for(int i=2;i<=y+1;i++){
        a[i]=1;
    }

    for(int i=2;i<=y+1;i++){
        if(a[i]==1){
            for(int j=2*i;j<=y+1;j+=i){
                a[j]=0;
            }

        }
    }

    for(int i=x;i<y+1;i++){
        if(a[i]==1){
            int ans=i,ans2=0;
            while(ans>0){
                int t;
                t=ans%10;
                ans/=10;
                ans2=ans2*10+t;
            }
            if(ans2==i){
                cout<<i<<endl;
            }
        }
    }
    return 0;
} 

by _Glassy_Sky_ @ 2022-11-19 17:48:16

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

by _Glassy_Sky_ @ 2022-11-19 17:48:48

题目上的


by eigw22h619 @ 2022-11-19 17:53:40

什么不看提示人

先找出所有回文数然后根号判断是不是质数


|