暴力做法
首先,一种偏暴力的做法:
将 $1 \sim b$ 中所有质数筛出来,分别判断即可。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, INF_BIT = 0x3f;
const int N = 1e8 + 10, M = 6e6 + 10;
int a, b;
int c[10], cnt;
bool ispal(int x){
cnt = 0;
while(x){
c[++cnt] = x % 10;
x /= 10;
}
//此处是否reverse不影响结果
for(int i = 1, j = cnt;i <= cnt / 2;i++, j--){
if(c[i] != c[j]) return false;
}
return true;
}
int p[M], ind;
bool f[N];
void shai(int n){
f[0] = f[1] = true;
for(int i = 2;i <= n;i++){
if(!f[i]){
p[++ind] = i;
if(a <= i && i <= b && ispal(i)){
printf("%d\n", i);
}
}
for(int j = 1;i * p[j] <= n;j++){
f[i * p[j]] = true;
if(i % p[j] == 0) break;
}
}
}
int main(){
scanf("%d%d", &a, &b);
shai(b);
return 0;
}
该代码(在AC Editor
上)运行5 100000000
这组数据所用的时间约为 $2.5 s$,肯定TLE,于是我们考虑优化。
优化算法
优化方法涉及到一个小知识:
偶数位的回文数一定不是质数(原因自己百度)
于是,我们如果发现输入的 $b$ 大于等于 $10 ^ 7$ 时,就让 $b$ 赋值为 $10 ^ 7$ 即可
代码(运行5 100000000
这组数据所用的时间约为 $100 ms$):
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, INF_BIT = 0x3f;
const int N = 1e8 + 10, M = 6e6 + 10;
int a, b;
int c[10], cnt;
bool ispal(int x){
cnt = 0;
while(x){
c[++cnt] = x % 10;
x /= 10;
}
for(int i = 1, j = cnt;i <= cnt / 2;i++, j--){
if(c[i] != c[j]) return false;
}
return true;
}
int p[M], ind;
bool f[N];
void shai(int n){
f[0] = f[1] = true;
for(int i = 2;i <= n;i++){
if(!f[i]){
p[++ind] = i;
if(a <= i && i <= b && ispal(i)){
printf("%d\n", i);
}
}
for(int j = 1;i * p[j] <= n;j++){
f[i * p[j]] = true;
if(i % p[j] == 0) break;
}
}
}
int main(){
scanf("%d%d", &a, &b);
if(b >= 1e7) b = 1e7; //偶数位的回文数一定不是质数
shai(b);
return 0;
}