c求助

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

prince_233 @ 2023-11-06 22:23:51

#include<stdio.h>
int main()
{
    int a,b,j,m,x[100000],q,k;
    scanf("%d %d",&a,&b);
    for(int i=a;i<=b;i++)
    {
        m=i;
            for(j=0;;j++)
        {
           x[j]=i%10;
           i=i/10;
           if(!i)
            break;
        }
        i=m;
        for(k=0;k<=j;k++,j--)
        {
            if(x[k]!=x[j])
            break;
        }
                 if(k>j)
        {
            for(q=2;q<m;q++)
                if(m%q==0)
                break;
                if(q==m)
                    printf("%d\n",m);
        }
    }
    return 0;
}

by prince_233 @ 2023-11-06 22:26:43

最后三个TLE,题解都看不懂,才学一个月不到,求大佬帮忙看看


by Code_Fish_GoodBye @ 2023-11-06 23:05:04

你这个肯定 TLE 啊,最坏复杂度都快到 10^9 了,你可以换种思路,既然它是让你求 1 \to 10^8 还得是回文的,不如我们就先构造一个回文的吗,就把你外面的那个循环范围弄小点,弄左边的,右边和左边的一样,判断它们是不是质数就可以了。


|