先递归求回文再判断素数。。。。。
第一章终于搞完了。。。。
Prime Palindromes
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 .
PROGRAM NAME: pprime
INPUT FORMAT
Line 1: | Two integers, a and b |
SAMPLE INPUT (file pprime.in)
5 500
OUTPUT FORMAT
The list of palindromic primes in numerical order, one per line.SAMPLE OUTPUT (file pprime.out)
5 7 11 101 131 151 181 191 313 353 373 383
HINTS (use them carefully!)
HINT 1 HINT 2/* ID: qhn9992 PROG: pprime LANG: C++11 */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; bool isprime(int x) { if(x==1) return false; int k=sqrt(x); for(int i=2;i<=k;i++) { if(x%i==0) return false; } return true; } int a[12],A,B,flag; void dfs(int n,int x) { if(!flag) return ; int ed=(n%2)? n/2+1:n/2; if(x==ed) { if(a[0]==0||a[n-1]==0) return ; int temp=0; for(int i=0;i<n;i++) temp=temp*10+a[i]; if(temp<A) return ; if(temp>B) { flag=0; return ; } if(isprime(temp)) printf("%d\n",temp); return ; } for(int i=0;i<=9;i++) { a[x]=a[n-1-x]=i; if(x==0&&a[x]%2==0) continue; dfs(n,x+1); } } int main() { freopen("pprime.in","r",stdin); freopen("pprime.out","w",stdout); scanf("%d%d",&A,&B); int w1=floor(log(A)/log(10))+1; int w2=floor(log(B)/log(10))+1; for(int i=w1;i<=w2;i++) { flag=1; dfs(i,0); } return 0; }