USACO/pprime

分析

这道题有两种思路：

1. 用筛法求出1..1e8范围内的素数，然后判断每个素数是否是回文数。
2. 生成1..1e8范围内的回文数，然后判断它是否是素数。

思路1的复杂度是O(n)，思路2的复杂度是O(√n*√n)=O(n)，从复杂度来看两种思路没有差别。但思路1用筛法用素数要开O(n)的数组，在n=1e8是就是90M，超出了空间限制，（而且有可能超时）,而思路2的空间复杂度是O(1)的，所以我们用思路2。

---

为什么思路1要O(n)的空间呢？是不是可以枚举一个一个素数，判断是否回文，是则写入pprime.out，然后枚举下一个。这样只要开一个9位数组就行了 （回答下因为用的方法是筛法吧by Lynk）

---

如何按照从小到大的顺序生成回文数呢？

设生成位数为l的回文数，若l是奇数，那么从小到大枚举(l+1) div 2位的数，然后复制翻转生成一个回文数；若l是偶数，那么从小到大枚举l div 2位的数，然后复制翻转生成一个回文数。上诉两个过程交替进行就可以从小到大生成回文数了。

很有效的优化：任意偶数长度的回文数都不可能为质数（除了11），因为它能被11整除，而11恰好只有自身和1两个因子。除2外，所有偶数均不可能是质数。

还有一个优化：尾数为5必不是质数。

生成回文数时可以用string[10]来记录，因为可以用insert（string,string,longint）函数，所以比较简便。

生成回文数时对于第一位，可以用case语句，对应1,3,7,9，另外的位就从0到9，直接转为字符，字符加起来再转为数字就行了

判断质数的时候有一个有效的优化，就是用筛法筛出1..10000(一万)以内的质数，再转存到数组q中，然后判断时只要用待判断的数mod q[n] 就可以了，这样很快，最大数据0.022s,700kb,代码见Pascal的"部分筛法"

第一种思路的可行性

直接使用筛法空间90M，但注意两点，一，题中最大size为1e8，实际上由于偶数长度无质数回文，偶数长度回文数均为11的倍数，所以只需开1e7即可。另外，可以使用位操作来存储和操作标记数组。使用这两点之后，直接暴力筛，按素数查询是否为回数，在不跳过偶数长度的情况下，0.356 secs, 4148 KB通过。比一般的第二种思路实现更快。

猥琐的解法

打表，将5~10^8之间的回文素数记录下来，在其中查找a和b，这个程序就不给了2015年6月22日 (一) 21:00 (CST)~{其实还是给了}

另一种解法

 思路同样是先生成回文，然后判断生成的回文是否是素数。但是生成回文的方法有些不一样：

我们先生成一个数组int p[7],其中p[0]表示回文的个位数，p[1]表示回文的十位数； 这样我们可以采用DFS进行搜索。因为回文具有 p[i]=p[digits-i-1], 所以DFS的深度为(digits-1)/2.假设所给最大数的位数为N，则在对N进行DFS的过程中， 我们事实上已经得到了位数M=1，2，..N的回文数。但是这样产生的回文并没有按照从小到大的顺序排列。 因此我们可以设置一个bool pp[9999999]的数组来判断，这样可以省去回文的排序。但是需要用new来分配空间。 同样使用了优化：1）所有偶数都不是质数，2）任意偶数长度的回文数都不可能为质数（除了11） 这种方法的时间还是比较好：[0.130 secs, 12700 KB]通过，可以参考代码（ｃ＋＋，ｈｅｒｏｈａｎ１）；

参考代码

C

C++

Pascal

Java