题目描述：给定一个区间，将这个区间里所有既是素数又是回文数的数输出来。
题目分析：这题的这个数据范围比较大，达到了10^8级别，而且输入的数据有多组，又因为判断一个数是否是回文数貌似只有暴力判断，时间限制是1000ms，所以如果对于每组数据输入都暴力判断的话，应该就TLE了，那么我们该怎么办呢。我们想到回文数本来就不多，再加上还必须要是素数，猜想数据范围虽然非常大，但是在这个区间里面满足条件的数应该不多，我算了一下，只有700多个，所以我们很自然地想到用离线打表，将这个区间内所有的满足条件的数存到一个数组里面去，然后输出的时候判断每一个数是否在输入的这个区间里面就可以了。
先给出本地打表代码：
#include<cstdio>
#include<cstring>
#include<math.h>
const int SIZE = ;
bool prim[SIZE];
void dabiao() { //先打素数表
memset(prim,,sizeof(prim));
for(int i = ;i<=SIZE;i+=)
prim[i] = ;
int d = sqrt(SIZE);
for(int i = ;i<d;++i) {
if(prim[i])
continue;
for(int j = i*i;j<SIZE;j+=i)
prim[j] = ;
}
}
bool judge(int k) { //判断是否是回文数
int num[],n = ;
while(k) {
num[n++] = k%;
k/=;
}
for(int i = ;i<n;++i)
if(num[i] != num[n-i-])
return false;
return true;
}
int main( ) {
int a,b;
freopen("file.txt","w",stdout); //将结果输出到文件中
dabiao();
int tot = ;
for(int i = ;i<=SIZE;++i)
if(!prim[i]&&judge(i))
printf("%d,",i);
return ;
}
下面是提交代码：
#include<cstdio>
int ans[] = {
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}; int main() {
int a,b;
while(scanf("%d%d",&a,&b)!=EOF) {
for(int i = ;i<=;++i)
if(ans[i]>=a&&ans[i]<=b)
printf("%d\n",ans[i]);
printf("\n");
}
return ;
}