C语言最后一个超时

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

hello098 @ 2023-10-07 22:53:43

#include <stdio.h>
#include <math.h>
int hw(int n);
int is(int n);
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);

    for(int i = a;i<=b;i++){
        if(hw(i)&&is(i)){
        printf("%d\n",i);
        }
    }
    return 0;
}
int hw(int n){
    int sum=0;
    int k=n;
    while(n!=0){
        sum=sum*10+n%10;
        n/=10;
    }
    if(sum==k) return 1;
    else return 0;
}
int is(int n){
    if(n%2==0) return 0;
    else{   for(int k = 3;k<=sqrt(n);k++){
            if(n%k==0){
                return 0;
            }
        }return 1;
    }
}

by Remarks @ 2023-10-07 23:09:53

@hello098 b-a的最大值达到1亿,O(n)算法最多能到5e7差不多,您应该按照题目中的做法,先生成回文数,再判断他是不是质数,降低时间复杂度


|