题意：给a，b。找出a - 》 b 范围内又是回文串又是素数的数。
看了看别人的博客，偶数个数组成的回文串一定不是素数。还有，开头是偶数的数，也不是，这个很容易想到。求素数的时候用到了唯一分解定理
算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。
所以我们只需要求到一个数n的sqrt（n）的素数，就可以利用这些素数判断n是否为素数。因为，如果2 - 》sqrt（n）没有n的因子，那么大于sqrt（n）是不可能出现两个因子的，所以只能是素数。
/** ID: DickensTone TASK: pprime LANG:C++ **/ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 10000 + 5; int palind[maxn]; int prime[maxn]; bool vis[maxn]; int cnt, p; void creat_prime() { p = 0; memset(vis, 0, sizeof(vis)); for(int i = 2; i < maxn; i++) { if(!vis[i]) { prime[p++] = i; int t = i; while(t < maxn) { vis[t] = 1; t = t * i; } } } } bool is_prime(int n) { for(int i = 0; i < p && prime[i] < n; i++) { if(n % prime[i] == 0) return false; } return true; } void creat_palind() { cnt = 0; for(int i = 2; i <= 11; i++) if(is_prime(i)) palind[cnt++] = i; for(int i = 1; i <= 9; i += 2)//3 { for(int j = 0; j <= 9; j++) { int t = i * 100 + j*10 + i; if(is_prime(t)) palind[cnt++] = t; } } for(int i = 1; i <= 9; i += 2)//5 for(int j = 0; j <= 9; j++) for(int k = 0; k <= 9; k++) { int t = i * 10000 + j * 1000 + k * 100 + j * 10 + i; if(is_prime(t)) palind[cnt++] = t; } for(int i = 1; i <= 9; i += 2)//7 for(int j = 0; j <= 9; j++) for(int k = 0; k <= 9; k++) for(int l = 0; l <= 9; l++) { int t = i * 1000000 + j * 100000 + k * 10000 + l *1000 + k * 100 + j * 10 + i; if(is_prime(t)) palind[cnt++] = t; } } int main() { freopen("pprime.in", "r", stdin); freopen("pprime.out", "w", stdout); creat_prime(); creat_palind(); int a, b; //printf("%d\n", prime[0]); //printf("%d\n", palind[0]); while(scanf("%d%d", &a, &b) == 2) { for(int i = 0; i < cnt; i++) { //printf("yes\n"); if(palind[i] >= a && palind[i] <= b) printf("%d\n", palind[i]); if(palind[i] > b) break; } } return 0; }