题目描述
蒜头君对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文数。回文数是指从左到右读和从右到左读都一样的数。现在小王想要你帮助他找出某个范围内的素数回文数,请你写个程序找出 aa 跟 bb 之间(包含 aa 和 bb)满足条件的数。
输入格式
输入 a 和 b(2 <= a <= b <= 100,000,000)
输出格式
按从小到大输出 a,b 之间所有满足条件的素数回文数,一个数占一行。
Sample Input
2 200
Sample Output
2
3
5
7
11
101
131
151
181
191
C++ 代码
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<cmath>
using namespace std;
const int MAX = 9998999;
int cnt = 0;//记录回文数的个数
int a[MAX];
bool prim(int x) //素数判断
{
int end = sqrt(x);
for(int j=2;j<=end;j++)
{
if(x%j==0)
return false;
}
return true;
}
bool judge(int x)//回文数判断
{
int k = x;
int ans = 0;
while(k)
{
ans = ans*10+k%10;
k/=10;
}
if(x == ans && prim(x)) //倒序与正序相等,即回文数,并判断是否为素数
return true;
return false;
}
int main()
{
int n,m;
for(int i = 2; i < MAX; i ++ )
{
if(judge(i))
a[cnt++] = i;
}
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<cnt;i++) //枚举所有的回文数,并在输入的范围内输出
{
if(a[i] >= n && a[i] <= m )
printf("%d\n",a[i]);
}
}
return 0;
}
解析
首先我们要注意题目所给的数据范围(100000000),这个数据量如果直接开数组的话可能会爆,所以先优化一下,想
一下距100000000最大的回文数,(这里有点小取巧QAQ),小10倍的我们就不考虑了,这里我们选取了999989999作
为数组的长度;
然后就是素数的筛选以及回文数的判断,这里就不一一讲解了,素数直接套它的判断模板,回文数的话,这里就会
有一些长的比较帅的小伙伴会用数组存它的每一位,然后前后比较,这里我们并不推荐这种方法,
我们用另一种方法,把这个数的每一位取出,然后倒序与它进行判断(回文数的特点),如果相等,即是回文数,
具体代码看上面,( **注意,这里要在判断回文数里面判断素数,如果边判断回文数边判断素数的话,容易TLM**);
接下来是从1~9998999判断是否是回文数** 并把它保存到数组里,记录其个数**(这一步是优化,为了减少之后不需
要的遍历) 最后,我们进行输入,枚举一下记录的个数,然后在输入的范围内进行输出,结束!