麻烦大佬帮忙康康,不会写

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

linyiyi123456 @ 2023-03-03 00:38:51

#include<stdio.h>
int A(int x)
{
    int i=2,ret=1;
    for(i=2;i<x;i++)
    {
        if(x%i==0)
        {
            ret= 0;
            break;
        }
    }return ret;
}
int B(int x)
{
    int i=1,cnt=1;
    int sum=0,ret=0;
    int t=x;
    int d=x;
    for(i=1;t>9;i++)
    {
        t/=10;
        cnt*=10;
    }
    while(d>0)
    {
        sum+=d%10*cnt;
        d/=10;
        cnt/=10;
    }if(sum==x)
    {
        ret=1;
    }
    return ret;
}
int main()
{
    int a,b;
    int i; 
    scanf("%d%d",&a,&b);
    for(i=a;i<=b;i++)
    {
        if(A(i))
        {
            if(B(i))
            {
                printf("%d\n",i);
            }
        }
    }
    return 0;
}

by Jorylee @ 2023-03-03 07:45:34

这个的复杂度差不多是 O(n^2) ,(每个数判断是不是质数是 O(n) ) 但是由题面可知 n 在1e8级别,所以肯定会超时。可以考虑参照题面上的提示1,先找到回文数再判断是否为质数


by Jorylee @ 2023-03-03 07:46:30

对于找回文数,可以发现回文数只要知道一半就可以生成整个回文数


by linyiyi123456 @ 2023-03-03 23:52:36

@Joryle 大佬,我可以说我没听懂么


|