55分超时了

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

spessert @ 2024-03-23 11:36:54

第一个评测点WA,后面三个是超时了,这代码还有什么优化的空间吗。

#include<iostream>
using namespace std;
int num[10];
bool juege(int x){ //判断回文 
    int i=0;
    while(x){
        num[i]=x%10;
        x/=10;
        i++;
    }
    for(int j=0;j<i/2;j++){  
        if(num[j]!=num[i-j-1]){
            return false;
        }
    }
    return true;
}
bool judge(int x){  //判断质数 
    if(x==1||x==0){
        return false;
    }
    if(x%2==0){
        return false;
    }
    for(int i=2;i<x/3+1;i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%2==0){
            continue;
        }
        if(i<10){
            cout<<i<<endl;
        }else if(juege(i)&&judge(i)){
            cout<<i<<endl;
        }
    }

    return 0;
}

by remake1958 @ 2024-03-24 20:33:00

你的代码在判断质数那一块可以继续优化,用eratosthenes筛法,,然后就是回文判断,其实可以用回文逆序等于本身判断,主函数也可以优化,减少不必要的计算


by spessert @ 2024-03-25 12:25:24

@remake1958 好的,感谢


|