超时了 大佬帮帮

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

zsj1337455772 @ 2024-12-04 17:00:07

#include<stdio.h>
#include<math.h>
int huiwen(int x)
{
    int i,sum=0,k=1,flag=0;
    int m=x;
    while(x>0)
    {
        i=x%10;
        x/=10;
        sum=sum*10+i;
    }
    if(m==sum) flag=1;
    return flag;
}
int zhishu(int n)
{
    int i,flag=1;
    if(n<2) flag=0;
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0) flag=0;
    }
    return flag;
}
int main()
{
    int a,b,i;
    scanf("%d %d",&a,&b);
    for(i=a;i<=b;i++)
    {
        if(zhishu(i) && huiwen(i)) printf("%d\n",i);
    }
    return 0;
}

by _lxc__ @ 2024-12-04 17:17:19

你这个时间复杂度直接飙到 O((b-a)\sqrt i) 了,肯定超时


by King_and_Grey @ 2024-12-04 17:17:34

@zsj1337455772

https://www.luogu.com.cn/article/5fw4hvxs


by _lxc__ @ 2024-12-04 17:18:00

所以建议先筛出回文数再判断质数


by Hanma @ 2024-12-04 17:21:48

无敌了


by fangzaixiazhong @ 2024-12-04 19:40:57

先判断回文,再判断质数


|