2.5 素數對
本節探討素數世家中兩類素數對：經典的孿生素數對與新穎的逆序素數對。
2.5.1 孿生素數對
相差為2的兩個素數稱為孿生素數對，簡稱孿生素數。例如，3與5是一對孿生素數，41與43也是一對孿生素數。
1. 孿生素數對是否無限的探討
素數有無窮多個，孿生素數對是有限還是無窮？
古希臘數學家歐幾里得曾猜想，存在無窮多對素數，它們只相差2，例如，3和5，5和7，2003663613×2195000-1和2003663613×2195000＋1，等等。
在1900年由數學家希爾伯特在國際數學家大會的報告上第8個問題中提出，可以這樣描述：存在無窮多個素數p，使得p＋2是素數。
這就是著名的孿生素數猜想，它與黎曼猜想、哥德巴赫猜想一樣，讓眾多數論學者與數學愛好者為之著迷。
據《自然》（Nature）雜志網站報道，來自美國新罕布什爾大學的華人數學家張益唐證明，存在無窮多個之差小于7000萬的素數對，從而在解決孿生素數猜想這一終極數論問題的道路上前進了一大步。
盡管從2到7000萬是一段很大的距離，《自然》的報道還是稱其為一個“重要的里程碑”。正如美國圣何塞州立大學數論教授Dan Goldston所言：“從7000萬到2的距離（指猜想中尚未完成的工作）相比于從無窮到7000萬的距離（指張益唐的工作）來說是微不足道的?！?/p>
到目前為止，這個常數已經從7000萬降到了246，越來越接近孿生素數猜想的范圍。如果這一常數改進到2，就相當于證明了孿生素數猜想成立。
目前已知最大的孿生素數共有388 342位數，通過分布式計算的Sophie Germain素數搜索項目于2016年9月14日發現孿生素數2 996 863 034 895×21 290 000±1。
2. 編程探求指定區間上的孿生素數對
（1）設計要點。
為擴大適應范圍，相關變量采用雙精度型。
應用試商法判定指定區間內的所有素數依次存儲到a數組。檢查a數組中若相鄰元素之差為2，即對應的這兩個素數相差為2，即為一對孿生素數。
（2）程序設計。
（3）程序運行示例與說明。
也可應用效率更高的篩法探求孿生素數對，有興趣的讀者不妨在以上應用篩法搜索素數程序的基礎上作變通實現。
2.5.2 逆序素數對
逆序素數對是構造特點更為有趣的素數對。
逆序數對：由兩個互為逆序數的不同整數組成的數對。例如，15與51是2位逆序數對，107與701是3位逆序數對。
逆序素數對：如果逆序數對的兩個整數都是素數，則稱逆序素數對（有些資料又稱回文素數對）。
注意到至少2位才能形成逆序，因此從最簡單的搜索2位逆序素數對開始討論。
【問題】 共有多少組2位逆序素數對？
【探求】 先應用前面的搜索法求出所有21個2位素數如下所示。
考慮到“逆序”，凡首位即十位數字為偶數或為5的（標注下畫線），其逆序非素數。因而可精簡到只查十位數字為1，3，7，9的素數。
從第一個素數開始，凡沒有標注下畫線的素數，逐個配對構建。
13與31為第1對2位逆序素數對；
17與71為第2對2位逆序素數對；
37與73為第3對2位逆序素數對；
79與97為第4對2位逆序素數對。
共有以上4組2位逆序素數對。
進一步，共有多少3位逆序素數對？在[100，2019]區間中共有多少逆序素數對？
【拓展】 探求指定區間[x，y]中的所有逆序素數對。
輸入正整數x，y（x＜y），試統計并輸出區間[x，y]中的所有逆序素數對（為避免重復，約定逆序素數對的較小素數在前，較大素數在后）。
1. 編程設計要點
（1）試商判別法搜索素數。
應用試商判別法搜索指定區間[x，y]中的所有素數（設共k個）存儲在p數組，p[j]是這k個素數的升序排列的第j個（1≤j≤k）。
同時，為判別方便，把與區間起點x相距為m-x的素數m標注q[m-x]＝1。
（2）產生逆序數。
對于素數d＝p[j]，設置條件循環（設初值r＝0），應用取整與取余運算在分離d的各個數字c的同時，求得其逆序數
while(d>0){c=d%10;r=r*10+c;d=d/10;}
則得素數p[j]的逆序數r。
（3）篩選與輸出。
設p[j]與其逆序數r構成逆序素數對（p[j]，r），根據約定p[j]＜r。
若素數p[j]的逆序數r非素數（q[r-x]?。?），或r≤p[j]，有違約定，返回。
否則，輸出逆序素數對（p[j]，r），并應用變量s統計逆序素數對的對數。
2. 程序設計
3. 程序運行示例與變通
順便指出，網上有資料稱Card經計算發現“有13對3位回文素數對”，這一結論明顯少了一對，應更正為14對。
進一步，可輸入區間[1001，9999]，探索到該區間4位逆序素數對共有102對。
程序設置搜索區間，使搜索范圍更廣。例如，可輸入區間[100，2019]，探索到該區間上逆序素數對共23對，其中3位的有14對，4位的有9對。
程序中應用了p數組存儲區間中的素數，注意區間中的素數個數k不能超過p數組的元素個數。
變通：把程序中篩選條件（q[r-x]?。?||r＜＝p[j]）修改為q[r-x]！＝1||r?。絧[j]，意味著輸出的素數p[j]的逆序數r就是其本身，此時素數p[j]即為對稱素數。