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 .
Line 1: | Two integers, a and b |
5 500
The list of palindromic primes in numerical order, one per line.
5 7 11 101 131 151 181 191 313 353 373 383
题解:判断回文素数
第一遍 用素数筛 筛出素数,然后判断是否回文。 超时.........
第二遍 找出回文数 然后判断是否为素数 超时....
之后才发现不用挨个找回文数 直接创造回文数 然后判断其是否为素数。超级快
/* ID: cxq_xia1 PROG: pprime LANG: C++ */ #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; int a,b; int lena,lenb; char creatN[10]; bool isprime(int n) //最朴素的方法判断素数 { if(n<a||n>b) return false; for(int i=2;i<=sqrt(n+0.0);i++) { if(n%i==0) return false; } return true; } int getNumLen(int n) //计算一个数的位数 { int len=0; while(n!=0) { n/=10; len++; } return len; } int getStrValue(int nowLen) { int value=0; for(int i=1;i<=nowLen;i++) { // value+=creatN[i]*pow(10.0,i-1.0); 不是很清楚pow函数,101他算出来是100。无奈用了下面的方法 int tmp=1; for(int j=1;j<i;j++) tmp*=10; value+=creatN[i]*tmp; } return value; } void creatPD2(int nowLen,int harfNowlen,int nowdigit) { for(int i=0;i<10;i++) { if(nowdigit==1&&i==0) continue; creatN[nowdigit]=i; creatN[nowLen+1-nowdigit]=i; if(nowdigit<harfNowlen) { nowdigit++; creatPD2(nowLen,harfNowlen,nowdigit); nowdigit--; } else { int tmp=getStrValue(nowLen); if(isprime(tmp)) cout << tmp << endl; } } } void creatPD1(int nowLen) { int harfNowLen; memset(creatN,0,sizeof(creatN)); harfNowLen=(nowLen+1)/2; creatPD2(nowLen,harfNowLen,1); nowLen++; if(nowLen>lenb) return; else creatPD1(nowLen); } int main() { freopen("pprime.in","r",stdin); freopen("pprime.out","w",stdout); cin >> a>> b; lena=getNumLen(a); lenb=getNumLen(b); creatPD1(lena); //创造回文数 return 0; }
原文:http://www.cnblogs.com/WillsCheng/p/4883899.html