一、题目描述
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
二、输入
There are multiple test cases.
Each case contains two integers, a and b.
a=b=0 indicates the end of input.
三、输出
For each test case, output the list of palindromic primes in numerical order, one per line.
例如：
输入：
5 500
0 0
输出：
5
7
11
101
131
151
181
191
313
353
373
383
四、解题思路
题意：输入两个数a和b，找出a-b之间的所有既是质数，又是回文数。当a = b = 0是退出。
思路：这道题看似简单，只需要找出a到b之间的质数，然后从中找出是回文数就OK了。可是题目有一个要求程序运行时间不能超过1秒，而且a,b的范围达到5-100,000,000，很容易超时，所以求质数要用最快的方法。我在这个超时上折腾了好长时间，差不多有两个小时。
1、判断是否是回文数
要判断数i是否是回文数，每一次操作不断地对其求取10的余数，产生新的数对原来的数进行翻转，翻转后的数跟原来的数比较，看是否相等，如果相等是回文数否则不是。如下图：
int num = i;
int temp = 0;
while(num)
{
temp *= 10;
temp += num%10;
num /= 10;
}2、判断是否是质数
有一个定理：如果一个数是合数，那么它的最小质数肯定小于等于的二次方根。
按照以上定理，如果一个数能被它的最小质因数整除，那它是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开根号后的所有数整除，这样做的运算练少很多从而提高了效率。
3、使用筛法求质数，用内存换时间
先建立一个boolean类型的数组，用来存储你要判断某个范围内自然数中的质数，例如，你要输出小于10000005的质数，你需要建立一个大小为10000005（建立10000005个存储位置是为了让数组位置与其大小相同）的boolean数组，初始化为true。是偶数的都不是质数。
其次用以上的方法求的第一个质数（例如3），然后将是3的倍数的数全置为false（2除外）位置上置为false。然后是3的倍数的全置为false（3除外），一直到10000005平方根，这样的话把不是质数的位置上置为false了，剩下的全是质数了
4、用一个大的数组保存
再求出其中是回文数的部分就是我们需要找的，再根据输入的a,b值，在数组中找出在a,b之间满足要求的回文质数。
五、代码
#include<iostream>
#include<math.h>using namespace std;#define maxn 10000005
bool isPrimeList[maxn]; //存放质数
int palindromeList[maxn]; //存放回文数int main()
{
int i;
isPrimeList[0] = false;
isPrimeList[1]= false;
isPrimeList[2] = true; for(i = 3; i < maxn; i+=2) //初始化质数
{
isPrimeList[i] = true;
isPrimeList[i+1] = false; //偶数不是质数
} int n = sqrt(maxn); //通过开根号求质数
for(i = 3; i < n; i+= 2)
{
if(!isPrimeList[i]) continue;
for(int j = i; j*i < maxn; j++)
{
isPrimeList[j*i] = false;
}
} int palCount = 0;
for(i = 0; i < maxn; i++) //求回文数组
{
int num = i;
int temp = 0;
while(num) //求num的翻转数
{
temp *= 10;
temp += num%10;
num /= 10;
}
if(i == temp && isPrimeList[i]) //这个回文数又是质数
{
palindromeList[++palCount] = i;
}
} int low, high;
cin >> low >> high;
while(low || high)
{
for(i = 0; palindromeList[i] < low; i++)
continue; for(;palindromeList[i]<= high && palindromeList[i]!=0;i++)
cout<<palindromeList[i]<<endl; cin >> low >> high;
} return 0;
}
