输出错了,求救

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

donghaoyu2011 @ 2023-02-08 17:18:48

还没评测就错了,样例输出多了一个9和121

#include <bits/stdc++.h>
using namespace std;
long long a,b,num[1000010];
bool find(long long x){
    long long cc=0,res1=0,res2=0;
    while(x!=0){
        cc++;
        num[cc]=x%10;
        x/=10;
    }
    for(int i=1;i<=cc;i++){
        res1*=10;
        res1+=num[i];
    }
    for(int i=cc;i>=1;i--){
        res2*=10;
        res2+=num[i];
    }
    if(res1==res2){
        return true;
    }
    else{
        return false;
    }
}
bool isprime(long long x){
    if(x==1){
        return false;
    }
    if(x==2){
        return true;
    }
    for(int i=2;i<sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(isprime(i)&&find(i)){
            cout<<i<<endl;
        }
    }
    return 0;
}

by donghaoyu2011 @ 2023-02-08 17:21:34

后来测了一下,33分。


by donghaoyu2011 @ 2023-02-08 17:22:18

要是开O2是44分


by olegekei @ 2023-02-08 17:28:27

for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }

by donghaoyu2011 @ 2023-02-08 17:42:59

@olegekei 谢谢


by donghaoyu2011 @ 2023-02-08 17:46:05

@olegekei 但是TLE怎么解决,怎么优化


by olegekei @ 2023-02-08 17:51:24

@donghaoyu2011

if(isprime(i)&&find(i))

改成if(find(i)&&isprime(i))

,另外读入的时候特判if(b>10000000) b=10000000;


by donghaoyu2011 @ 2023-02-08 17:57:16

@olegekei 谢谢,但能告诉我为什么要把 if(isprime(i)&&find(i))改成if(find(i)&&isprime) 吗?


by olegekei @ 2023-02-08 18:02:44

@donghaoyu2011 暴力check每一个数字是否是质数最坏是O(sqrt(n)),但是check每一个数字是否是回文数只需要O(a(≤7)),后者比前者快得多,

而把find放到isprime前面,程序会先执行find,如果find已经返回了false就不再进行isprime,大大优化了程序效率


|