AcWing 1356. 回文质数(要短的,看这里)
原题链接
简单
作者:
吴鑫
,
2021-02-09 12:07:04
,
所有人可见
,
阅读 489
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e8+10,M=N/log(N)+10;//一般有 N/lnN 个素数(常识)
int a,b;
int prime[M],cut;
bool st[N];
void get_prime(){ //线性筛
for(int i=2;i<=b;i++){
if(!st[i]) prime[cut++]=i;
for(int j=0;prime[j]<=b/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}
int main(){
cin>>a>>b;
if (b > 10000000) b=10000000; //偶数位的回文数不是素数,直接去掉
get_prime();
int t=lower_bound(prime,prime+cut,a)-prime;
for(int i=t;i<cut;i++){
int k=prime[i];
int ans=0;
for(;k;k/=10) ans=(ans*10+k%10); //制造回文数
if(ans==prime[i]) printf("%d\n",ans);
}
return 0;
}