2.4 素数变形金刚
本节探讨构形上能经受指定系列变形的两类素数变形金刚——金蝉素数与超级素数，这两类素数是素数世家中的优美子集。
2.4.1 金蝉素数
某古寺的一块石碑上依稀刻有一些神秘的自然数。
专家研究发现：这些数是由1，3，5，7，9这5个奇数字排列组成的5位素数，且同时去掉它的最高位与最低位数字后的3位数还是素数，同时去掉它的高二位与低二位数字后的一位数还是素数。因此，人们把这些神秘的素数称为金蝉素数，意即金蝉脱壳之后仍为金蝉。
试求出石碑上的金蝉素数。
1. 设计要点
本题求解的金蝉素数是一种极为罕见的素数，实际上是5位素数的一个子集。
设置5位数k循环，对每一个k，进行以下判别。
（1）分离k的5个数字，检查5个数字中是否存在偶数字与相同数字。
（2）分离的5个数字正中的数字是否为1与9（奇数字中1，9非素数）。
（3）应用求余运算对5位数d（d＝k；）实施脱壳成为3位数，应用试商判别法判定5位数d及其脱壳的3位数d是否为素数。
设置标志量t，t赋初值t＝0。每一步检查若未通过，则t＝1。
最后若t＝0，则打印输出k即为金蝉素数。
2. 金蝉素数程序设计
3. 程序运行结果与说明
5位金蝉素数为:
13597 53791 79531 91573 95713
共以上5个。
这5个金蝉素数中的5个奇数数字没有重复，且经一次、二次脱壳后仍是素数。
例如，13 597为素数，一次脱壳后得359为素数，二次脱壳后为5仍是素数。
顺便指出，在这5个金蝉素数中，13 597与79 531是互逆的金蝉素数。
2.4.2 超级素数
定义m（m＞1）位超级素数如下所示。
（1）m位超级素数本身为素数。
（2）从高位开始，去掉1位后为m-1位素数；去掉2位后为m-2位素数；……；去掉m-1位后为1位素数。
例如，137是一个3位超级素数，因137是一个3位素数；一次变形去高1位得37是一个2位素数，二次变形去高2位得7是一个1位素数。
而素数107不是超级素数，因去高1位得7不是一个2位素数。
输入整数m（1＜m≤16），统计m位超级素数的个数，并输出其中最大的超级素数。
我们应用效率较高的递推算法设计求解。
1. 递推设计要点
根据超级素数的定义，m位超级素数去掉高位数字后是m-1位超级素数。一般地，k（k＝2，3，…，m）位超级素数去掉高位数字后是k-1位超级素数。
那么，在已求得g个k-1位超级素数a[i]（i＝1，2，…，g）时，在a[i]的高位加上一个数字j（j＝1，2，…，9），得到9∗g个k位候选数f＝j∗e[k]＋a[i]（e[k]＝10k-1），只要对这9∗g个k位候选数检测即可。这就是从k-1递推到k的递推关系。
注意到m（m＞1）位超级素数的个位数字必然是3或7，则得递推的初始（边界）条件为a[1]＝3，a[2]＝7，g＝2；个位数字5虽然是素数，但加任何高位数字后就不是素数，因而不予考虑。
2. 递推程序设计
3. 程序运行示例与说明
请确定位数m(1<m<16):9
共545个9位超级素数。
其中最大数为999962683。
应用递推设计探求k位超级素数时，只需检测9∗g（k-1）个（其中g（k-1）为k-1位超级素数的个数），由于g（k-1）数量不大，因而程序简便快捷。
例如，当m＝5时，应用递推设计调用p（k）函数次数仅9∗（2＋11＋39＋99）＝1359，比枚举5位奇数的数量小得多。
输入的位数m可大于9，最多可达15位，但程序运行时间会变得比较长。