TLE了该怎么优化,,

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

sanammm @ 2022-10-24 19:00:06

#include<stdio.h>
int hws(int n)
{
    int s=0;
    for(int i=n;i>0;i/=10)//数倒置判断是否相等
    {
        s=s*10+i%10;
    }
    if(s==n) return 1;
    else return 0;
}
int ss(int n)
{
    for(int i=2;i*i<n;i++)
    {
        if(n%i==0) return 0;
    }
    return 1;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    if(m>=5) printf("5\n");
    if(m>=7) printf("7\n");
    if(m>=11) printf("11\n");
    for(int i=101;i<=m;i+=2)
    {
        if(i%11!=0)
            if(ss(i) && hws(i)) printf("%d\n",i);
    } 
    return 0;
}

by HJY2022 @ 2022-10-24 19:03:11

@sanammm 你只要枚举到1e8就好了吧,到M怕不是要T


by HJY2022 @ 2022-10-24 19:04:29

@sanammm 不过你构造回文数应该会快很多


by sanammm @ 2022-10-24 19:05:03

@_HJY2022 m最大不是1e8吗


by HJY2022 @ 2022-10-24 19:08:14

@sanammm 枚举到1e7,我sb了(偶数位没有回文质数)


|