求助 最后一个超时 已经用了质数筛了

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

Lolaandd @ 2024-08-21 16:51:23

#include<iostream>

using namespace std;

const long int maxn=100000000;

long int a,b;
bool visit[maxn];
long int prime[maxn];
int sieve(int min,int max)
{
    long int i,j,k=0;
    visit[0]=visit[1]=1;
    for(i=2;i<=max;i++)
    {
        if(visit[i]==0)
        {
            prime[k++]=i;
            for(j=i;i*j<=max;j++) visit[i*j]=1;
        }  
    }
    return k;
}

int check_pld(int a)
{
    int list[100]={0};
    int len=0;
    while(a>0)
    {
        list[len++]=a%10;
        a/=10;
    }
    int flag=1;
    for(int i=0;i<len/2;i++) if(list[i]!=list[len-1-i]) {flag=0; break; }
    return flag;
}
int main()
{
    cin >>a>>b;
    int num=sieve(a,b);
    for(int i=0;i<num;i++) if(prime[i]>=a) if(check_pld(prime[i])==1) cout<<prime[i]<<endl;
    return 0;
}

by dongzirui0817 @ 2024-08-21 16:54:51

@Lolaandd 先搜回文数再看是不是质数(回文数不多,但搜质数容易超时)


by mm1221 @ 2024-08-21 16:54:57

实在不行就改成线性筛法(?)

可参照这位大佬的blog


by dongzirui0817 @ 2024-08-21 16:58:27

@mm1221 有时候欧拉筛还没埃式筛快


by dongzirui0817 @ 2024-08-21 16:59:56

因为模的用时比较长


by Yue_Hao @ 2024-08-21 17:01:38

@Lolaandd ,我也是同样的问题,我给个建议:1.这个你先判断回文数,再判断质数效率快一点;2.判断质数的时候,只要循环到这个数的二次根后的结果就可以了( ceil(sqrt(x)) )


by mm1221 @ 2024-08-21 17:01:50

@dongzirui0817 但我记得基本上都是线性筛快\ 埃氏筛法:\Theta{(n \log \log n)}\ 线性筛法:\Theta{(n)}

本人L^AT_EX小白,请多指教


by dongzirui0817 @ 2024-08-21 17:04:08

@mm1221 你说的对(虽然本来就对),但欧拉筛被模浪费了速度,所以有时候也没快多少(我也对此无语啊)


by Lolaandd @ 2024-08-21 19:40:33

@dongzirui0817 谢谢!


by Lolaandd @ 2024-08-21 19:40:48

@mm1221 好 我试试 谢谢!


by Lolaandd @ 2024-08-21 19:41:05

@Yue_Hao 我试试看 谢谢啦!


|