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位，但程序運行時間會變得比較長。