回文素数 prime palindrome（构造回文数）

题目描述：

给定x，y，输出[x，y]中所有的回文素数（即既是回文数也是素数，比如101， 131），其中5 <= a < b <= 1000000000 时间限制：5s 内存限制：512M

思想：

1.暴力枚举所有的数据

考虑从5~1e9枚举，先判断是不是回文数，然后判断是不是素数，然后输出（当然也可以反过来，先判断是不是素数然后判断是不是回文数），这里时间上肯定会有差别，首先回文数与素数的密度是不一样的，以及，判断回文数与判断素数的时间复杂度也是不一样的，那么这里的时间复杂度至少是O(n)的（其实大很多），可以考虑一下时间限制，肯定是过不了的（至少要几十秒）。当然这也是最容易想到的办法。

2.给定素数

假设我们只需要判断其中一个呢，首先考虑给定素数，然后去判断回文数，于是乎我们想到了打素数表，然后去直接去表里面找到素数然后判断是不是回文数即可（那为什么不直接存所有的回文素数然后直接输出呢）。很显然这样是不行的，因为会被手动ban掉。

3.给定回文数

这与做法2有什么不一样呢？当然有，素数我们只能先存下来，然后直接使用，但是回文数我们不需要存，因为它可以被构造出来，比如101，那么可以由10得到（即10*10+1），再比如12321可以由123得到，当然同样可以枚举位数为偶数的回文数如1221，但是这里有一个数学定理，即所有偶数位的回文数都是11的倍数（除了11，除非你认为它是一倍），其实不知道这个定理也无妨，假设偶数位数的回文数和奇数位一样多，那么我们顶多就增加一倍的时间，可是我们已经解决了最大的问题就是去遍历1e9，为什么这么说呢，因为你会发现，要构造1e9的回文数，只需要1e5的数据量，即1 000 000 00 1可以由100000得到，所以说我们只需要从5遍历到100000即可，这也就是为什么我们说增加一倍的时间不重要的原因了，因为相比于1e9，多跑一遍1e5要快得多，那么我们就确定了解决的方式，即构造回文数，然后判断是否是素数即可。（不会真有人不会构造回文数吧？），不必考虑从什么时候开始，不妨每次都从5开始，其实影响并不大，只要回文素数大于x再输出即可。当然不必每次都枚举到1e5，适当时候break即可。当然11是需要额外判断的。

构造回文：

1234 -> 12343 -> 123432 -> 1234321

4.代码

#include<stdio.h> int is_prime(int x) { if(x == 2) return 1; for(int i = 2; i*i <= x; i++) { if(x % i == 0) return 0; } return 1; } int main() { int a, b; scanf("%d%d", &a, &b); for(int i = 5; i <= 100000; i ++) { if(i == 9 && a <= 11 && b >= 11) puts("11"); int tmp = i/10, ans = i; while(tmp > 0) { ans *= 10; ans = ans + tmp%10; tmp /= 10; } if(ans > b) break; if(ans >= a && is_prime(ans)) printf("%d\n", ans); } return 0; }