最后一点tle求调(c++)

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

xzq4121 @ 2023-10-14 11:08:19

c++代码:

#include <bits/stdc++.h>
using namespace std;
int a,b,c,d,e[7],f=0,h=0,i;
char g[100000010];
int main(){
    cin>>i>>b;
    g[1]=1;
    for(a=2;a<=b;a++){
        if(g[a]==0){
            c=b/a;
            for(d=2;d<=c;d++) g[a*d]=1;
        }
    }
    for(a=i;a<=b;a++){
        if(g[a]==0){
            d=a;
            c=0;
            while(d!=0){
                c++;
                e[c]=d%10;
                d=d/10;
            }
            for(d=1;d<=c;d++){
                if(e[d]!=e[c-d+1]) h=1;
            }
            if(h==0) cout<<a<<endl;
            h=0;
        }
    }
    return 0;
}

by BugGod @ 2023-10-14 11:11:00

这复杂度高于 O(b),明显会 TLE 啊。


by Mr_RedStone @ 2023-10-14 11:34:14

8-13行的筛法太慢了


by Mr_RedStone @ 2023-10-14 11:35:21

改成线性筛


by xzq4121 @ 2024-11-20 14:57:27

@Mr_RedStone 艹,太唐了,现在才又看到这道题,用线性筛 A 了,此帖结。


|