求助最后一个超时害

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

dreamlike @ 2023-02-11 03:35:48

个人思路就是先检验是否为回文数，再检验是否为质数。回文数是用倒置来验证，数目大是建议用字符串，但这道题是整数递增来一个个验证的，数据类型匹配不了，我脑子实在没能转过来害；质数的话已经是平方减半了，不知道还能不能优化。目前最后一个超时是1.02s，测试数据是5 100000000，卑微请各位大佬赐教！代码如下：

#include<stdio.h>
int prime(int x){
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0) return 0;
    return x<=1?0:1;
}
int isHuiwenNumber(int n)
{
    int sum,tmp;
    tmp=n;
    sum=0;
    while(n)  //从低位到高位分解n的每位的数字,然后依次相加
    {
        sum=sum*10+n%10;
        n/=10;
    }
    if(tmp == sum) //如果重新每位求和的值等于原值,则该数为完数,返回1,否则返回0
        return 1;
    else
        return 0;
}
int main(){
    int a,b,i;
    scanf("%d %d",&a,&b);
    for(i=a;i<=b;i++)
    {
        if(isHuiwenNumber(i))  
        {
            if(prime(i))
                printf("%d\n",i);
        }
    }
}

by Usada_Pekora @ 2023-02-11 03:48:46

@dreamlike 枚举ab中所有的奇数。

by Usada_Pekora @ 2023-02-11 03:49:52

#include<stdio.h>
int prime(int x){
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0) return 0;
    return x<=1?0:1;
}
int isHuiwenNumber(int n)
{
    int sum,tmp;
    tmp=n;
    sum=0;
    while(n)  //从低位到高位分解n的每位的数字,然后依次相加
    {
        sum=sum*10+n%10;
        n/=10;
    }
    if(tmp == sum) //如果重新每位求和的值等于原值,则该数为完数,返回1,否则返回0
        return 1;
    else
        return 0;
}
int main(){
    int a,b,i;
    scanf("%d %d",&a,&b);
    if(a%2==0)a++;
    for(i=a;i<=b;i+=2)
    {
        if(isHuiwenNumber(i))  
        {
            if(prime(i))
                printf("%d\n",i);
        }
    }
}

by dreamlike @ 2023-02-11 03:58:56

@Usada_Pekora 试了下，减半后但还是超时，应该还是出在检验质数还是回文数的操作上害

by Usada_Pekora @ 2023-02-11 05:33:32

@dreamlike https://www.luogu.com.cn/record/101875174

写暴力不开 O2？

by Nwayy @ 2023-02-11 07:08:39

@dreamlike 显然这道题没有必要从 a 搜到 b，欧拉筛筛出质数后直接从已知质数中找是否回文且小于 b 即可，还有就是如果 b \ge 10^8 可以直接缩小为 10^7。

by 大眼仔Happy @ 2023-02-11 07:16:10

有没有可能先找出所有的回文数，再判断

by dreamlike @ 2023-02-11 14:18:37

@Usada_Pekora 哦吼！没玩明白O2优化，谢谢！

by dreamlike @ 2023-02-11 14:21:43

@winds888 你好，其他的懂了，方便问问“如果 b≥10^8 可以直接缩小为10^7”的原因么

by Nwayy @ 2023-02-11 14:52:52

@dreamlike 说错了，后面那句话不用管

by dreamlike @ 2023-02-11 16:08:40

@winds888 好滴谢谢！