c++实现找出一亿以内的所有回文质数【算法思想+源码】

题目描述：

因为151即是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。
写一个程序来找出范围[a,b](5 <= a < b <= 100000000)间的所有回文质数。

时限：1000ms 内存限制：10000K 总时限：3000ms

输入：

 单独一行，两个长整型数，a，b（以空格隔开）。

输出：

 从小到大，输出一个回文质数的列表，一行一个。

输入样例：

 5 500

输出样例：

5 7 11 101 131 151 181 191 313 353 373 383

注意的问题： 

对于这道题，想要用常规的方法（从a开始一个一个找回文数，然后判断是不是质数）显然是不现实的，算然这种方法思路很简单，但肯定会超时。那么就需要换种思路来解这道题，可以从一下方面考虑问题。

• 对于先找回文数再判断是否是质数还是先判定是否是质数再判断是否是回文数的顺序问题，推荐顺序是先找回文数再判断是否是质数；
• 偶数个数字的数既是回文数又是质数的数字仅仅只有11，因为所有偶数个数字的回文数都能被11整除（即不是质数），比如二位数的22、33，四位数的1221，六位数的1234321等均能被11整除，这使得回文质数只需要从1，3，5，7位数的数字中找，这大大的节省了运行时间（一亿范围内，一千万以后不会有回文质数）。因此实际上仅仅需要在一千万的范围内找回文质数即可，这再一次大大减少程序运行时间。
• 判断素数的条件位for（i=0;i<sqrt(n);i++）（n为需要判断的数）。

基于上述思想，我的AC代码： 

#include <iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
	for(int i = 2;i<=sqrt(n);i++)
	{
		if(n%i == 0)
		{
			return false;
		}
	}
	return true;
}
int myPow(int n)
{
	int temp = 1;
	for(int i = 0;i <n;i++)
	{
		temp*=10;
	}
	return temp;
}
//判断n是不是回文质数 k表示该数是几位数 
void isPalindrome(int k,int a,int b)
{
	int x = (myPow(k)-1);
	int n = b<x ? b : x;
	int i = myPow(k-1);
	int temp,num;
	for(int j = i;j<=n;j++)
	{
		if(j>=a&&j<=b&&j%2!=0)
		{
		temp = j;
		num = 0;
		while(temp>0)
		{
			num=num*10+temp%10;
			temp/=10;
		}
		if(num == j&&isPrime(j))
		{
			cout<<num<<endl;	
		}
		}
	} 
	return;
}
int main()
{
	int n,m,temp_n,temp_m,x,y;
	cin>>m>>n;
	x = 0;
	y = 0;
	int elevle= 11;
	temp_m = m;
	temp_n = n;
	while(temp_m!=0)//计算m为几位数 
	{
		x++;
		temp_m/=10;
	}
	while(temp_n!=0)//计算n为几位数 
	{
		y++;
		temp_n/=10;
	}
	if(n>10000000)//一千万以后无回文质数 
	{
		n = 9999999;
		y = 8;	
	} 
	for(int i = x; i<=y; i++)//找x位数到y位数之间所有的回文质数 
	{
		if(i==2&&m<=elevle&&n>=elevle)
		{
			cout<<elevle<<endl; //对于两位数的回文质数仅有11 
		} 
		else if(i%2!=0)//偶数个数字的数没有回文数 
		{
				isPalindrome(i,m,n);
		}
	}
	return 0;
}