最后两个点超时了!!麻烦大佬看一眼

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

b1adez @ 2024-01-25 23:08:59

#include <stdio.h>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

bool isPrime(int num){
    if(num<=1){//小等于1都不是质数 
        return false;
    }
    if(num==2){//2是最小质数 
        return true;
    }
    if(num%2==0){//排除所有偶数 
        return false;
    }

    int sqrtNum = sqrt(num);
    for(int i=3;i<=sqrtNum;i++){
        if(num%i==0){
            return false;//false直接就结束所有循环了,下面的true也不会执行 
        }
    }
    return true;

}
//此题给定范围都在int之内,所以使用反转取等来判断回文数
bool isHuiwen(int num){
    int temp = num; 
    int reverse = 0;
    while(temp!=0){//num==0的时候就是num所有位都被取出了 
        reverse = reverse*10+temp%10;
        temp/=10;
    }
    if(num==reverse){
        return true;
    }
    return false;//
} 

int main(){
    int a,b;
    cin>>a>>b;//范围
    for(int i=a;i<=b;i++){
        if(isPrime(i)&&isHuiwen(i)){//是质数也是回文数 
            cout<<i<<endl;
        }
    } 
}

by xueshengyi @ 2024-01-26 00:01:55

把判断的顺序换一下可以多过2个点

但仍然超时,建议打表/筛法求质数


|