88求助,C,最后一个超时了

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

P_udding @ 2024-02-25 22:25:51


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    //从奇数开始
    if(a%2==0){
        a++;
    }
    //枚举奇数
    for(;a<=b;a+=2){
        //判断位数
        int m=a;
        int q=0;
        while(m>=10){
            m/=10;
            q++;
        }
        //判断回文
        int n=a;
        int k=0;
        for(;q>=0;q-=2){
            if(n/(int)pow(10,q)!=n%10){
                k=1;
                break;
            }
            n=n%(int)pow(10,q)/10;
        }
        //判断质数
        if(k==0){
            int f=0;
            for(int j=2;j<=(int)pow(a,1.0/2);j++){
                if(a/j==a*1.0/j){
                    f=1;
                    break;
                }
            }
            if(f==0){
                printf("%d\n",a);
            }
        }
    }
    return 0;
}

by K_func @ 2024-02-27 20:01:00

@P_udding 时间复杂度不行,考虑用下欧拉筛


by P_udding @ 2024-02-27 20:19:26

@Jadejunxi 好的,我之前只是知道这个还没有自己用过,我写写试试,感谢


|