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 但我记得基本上都是线性筛快\
埃氏筛法:
本人
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 我试试看 谢谢啦!