88分，最后一个TLE！（说出错误必关）

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

fifast @ 2024-10-06 11:35:07

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        int ti=i,num=0;
        while (ti!=0){
            num=num*10+ti%10;
            ti=ti/10;
        }
        if(num==i){
            bool m=1;
            for(int j=2;j<=sqrt(i);j++){
                if(i%j==0){
                    m=0;
                    break;
                }
            }
            if(m==1)cout<<i<<endl;
        }
    }
    return 0;
}

by zts201210 @ 2024-10-06 11:38:27

@fifast 有没有一种可能，这道题不能用暴搜

by fifast @ 2024-10-06 11:41:48

@zts201210 我没有暴搜，我是按题目从a到b的!

by zts201210 @ 2024-10-06 11:43:30

@fifast 我说的意思是，你不能用暴力判断质数

by feizhu_QWQ @ 2024-10-06 11:43:50

你这不超才怪。
第一层循环就有一亿的时间复杂度，还在里面套一个质数判断，质数判断是有根号的时间复杂度的。
所以粗劣计算时间复杂度极限情况应该是：

我可以提供一下我的代码： ```cpp #include<bits/stdc++.h> using namespace std; int a[1000005]; bool su(int x) { if(x<=1) return false; for(int i=2;i*i<=x;i++) { if(x%i==0) return false; } return true; } int main() { int cnt=0; for(int i=5;i<=9;i+=2) a[++cnt]=i; for(int i=1;i<=9;i+=2) { a[++cnt]=i*10+i; } for(int i=1;i<=9;i+=2) { for(int j=0;j<=9;j++) { a[++cnt]=i*100+j*10+i; } } for(int i=1;i<=9;i+=2) { for(int j=0;j<=9;j++) { a[++cnt]=i*1000+j*100+j*10+i; } } for(int i=1;i<=9;i+=2) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { a[++cnt]=i*10000+j*1000+k*100+j*10+i; } } } for(int i=1;i<=9;i+=2) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { a[++cnt]=i*100000+j*10000+k*1000+k*100+j*10+i; } } } for(int i=1;i<=9;i+=2) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { for(int l=0;l<=9;l++) { a[++cnt]=i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i; } } } } for(int i=1;i<=9;i+=2) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { for(int l=0;l<=9;l++) { a[++cnt]=i*10000000+j*1000000+k*100000+l*10000+l*1000+k*100+j*10+i; } } } } //上面是枚举所有的回文数 int l,r; cin>>l>>r; for(int i=1;i<=cnt;i++) { if(su(a[i])==true&&a[i]>=l&&a[i]<=r) cout<<a[i]<<endl;//质数判断，不用a到b } return 0; } ``` ~~我用枚举做的~~ @[fifast](/user/1402877)

by dongzirui0817 @ 2024-10-06 11:44:02

@fifast 本来就不能从 a 到 b 爆搜，毕竟 a,\, b \le 10^8 啊（建议去题解学正解）

by fifast @ 2024-10-06 11:54:36

多谢@zts201210 @feizhu0130 @dongzirui0817 以关！（求互关）

|