题目链接如下https://www.luogu.org/problemnew/show/P1217
找出a到b 是回文数并且是素数的数。
这还不简单 前两天刚学的线性筛素数。卡卡卡卡一顿猛敲。最后一个测试点TLE了。我无语了。。。。。。。
改吧。
自古评论区里出人才。
判断素数也有几个小结论。如下：
1.偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000。
2.偶数肯定不是质数。这样至少排除一半多的数据量。
3，你回文数已经判断出来了，在此中判断即可。
#include <iostream>
using namespace std;
int check[100000010];
void is_prime(int n){
for(int i=2;i*i<=n;i++){
if(check[i]){
continue;
}
for(int j=i*i;j<=n;j+=i){
check[j]=1;
}
}
}
int main(){
int a,b;
cin>>a>>b;
if(b>10000000){
b=9999999;
}
is_prime(b);
if(a%2==0){
a++;
}
for(int i=a;i<=b;i+=2){
if(check[i]==0){
int sum=0;
int temp=i;
while(temp!=0){
int yu=temp%10;
temp=temp/10;
sum=sum*10+yu;
}
if(sum==i){
cout<<i<<endl;
}
}
}
} 一般来说是时间复杂度是忽略系数的，这个题是个例外。。。。
N 不过 ，必须是O（N）