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 <= 1000,000,000); both a and b are considered to be within the range .
Input
Line 1: Two integers, a and b
Output
The list of palindromic primes in numerical order, one per line.
Sample Input
5 500
Sample Output
5 7 11 101 131 151 181 191 313 353 373 383
分析：这道题从昨天下午一直困扰我到今天中午，第一次打直接暴力搜索，超时。后来查阅一些资料，发现原来的暴搜需要一些剪枝，首先除了11以外的所有位数为偶数的回文数都不是质数。
证明：先设出一般形式：an...a2a1a1a2...an.然后可将其改写(首尾两两依次配对)：
an...a2a1a1a2...an=an*(10^(2n-1)+1)+...+a2*(10^(2*2-1)+1)*10^(n-2)+a1*(10^(2*1-1)+1)*10^(n-1)
可以看到求和的每一项均有因式10^(2k-1)+1,而该因式可以化为（11-1）^(2k-1)+1,进行二项式展开就可以得证了.这样一来我们的时间复杂度会得到大幅度降低。
还有一点就是我们不需要判断回文数，而是需要构造符合条件的回文数，然后判断其是否是素数。这样假如我们需要判断5-1000000000的范围，我们只需要5-100000即可。我的代码是这样的：
#include <stdio.h> #include <math.h> int prime(int a) { int i; for(i=2;i<=sqrt(a);i++) if(a%i==0) return 0; return 1; } int getlength(int a) { int count=0; do{ a/=10; count++; } while(a); return count; } int gethigh(int a) { do{ a/=10; } while(a/10!=0); return a; } int main() { int i,a,b,len,t,sum,tmp; scanf("%d %d",&a,&b); len=getlength(b); if(len%2) len=(len+1)/2; else len=len/2; //数据只需要枚举到一半翻折构造回文数 t=pow(10,len); for(i=a;i<t;i++) { if(i==5||i==7) printf("%d ",i); else if(i==9) printf("%d ",11); else{ for(sum=i,tmp=i/10;tmp!=0;tmp/=10){ sum=sum*10+tmp%10; } if(prime(sum)&&sum<=b&&sum>=a) printf("%d ",sum); else if(sum>b) break; else continue; } } return 0; }
AC了，但我其实还是不满意，因为我的代码枚举到1000000000需要30多秒，网上有很多其他的方法，但大都是C++实现的。这也体现出CPP在解决算法竞赛方面的巨大优势，还有一些地方可以完善比如首位为2,4,6,8,5的数其实不需要我们翻折，因为他们肯定不是素数。所以这些地方都可以优化，但我现在的代码结构貌似没法进行这种优化了。希望能有人写出完美的优化吧。