题目描述
151 既是一个质数,又是一个回文数,因此它可以被称为回文质数。
现在给定两个整数 a,b ,请你找出在 [a,b] 范围内的所有回文质数。
输入格式
共一行,包含两个整数 a,b。
输出格式
按照从小到大的顺序输出所求范围内的所有回文质数。
每个数占一行。
数据范围
5≤a<b≤10^8^
输入样例:
5 500
输出样例:
5
7
11
101
131
151
181
191
313
353
373
383
算法
本题数据范围大,直接找会超时。
1.根据位数为偶数的回文数,必定能被11整除这一数学性质,可以将数据范围缩小到10的7次方。
2.再使用线性筛算法筛选出质数表提高判断质数的效率。
3.质数的个数约是N / lnN,再加上判断回文的复杂度,整体时间复杂度不超过10的7次方。
C++代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e7 + 10;
int p[N], cnt;//p[]:质数表
bool st[N];
void init(int n)//筛质数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) p[cnt ++ ] = i;
for (int j = 0; p[j] <= n / i; j ++ )
{
st[p[j] * i] = true;
if (i % p[j] == 0) break;//保证只被最小的质数筛掉
}
}
}
bool check(int x)//判断回文
{
string s = to_string(x);
for (int i = 0, j = s.size() - 1; i < j; i ++, j -- )
if (s[i] != s[j])
return false;
return true;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
init(N);
for (int i = 0; i < cnt; i ++ )
{
if (p[i] >= a && p[i] <=b && check(p[i]))
printf("%d\n", p[i]);
}
return 0;
}