關于如何尋找質數的一種嘗試

易照雄

摘 ?要：從小于20的八個已知質數出發，由數值計算去嘗試尋找質數（包括孿生質數）的公式與簡便方法。

關鍵詞：質數;偽質數;贋質數;數值計算

一、關于質數的公式

質數（或稱之為素數）是指只能被1和其自身所整除的自然數。而合數則是指通過若干個質數相乘所構成的、可以被拆分的自然數。正是在這個意義上，人們將質數視為數學中的“原子”-------一切數的基礎。通過考察已知的質數不難看出，所有兩位及兩位以上的質數的個位數只能是1、3、7、9，無一例外。而個位數為0、2、4、5、6、8的自然數以及開方后為整數的自然數，均無一例外為合數。數值計算表明，所有大于10的質數似都可以由公式 ? 給出。只不過該公式在給出所有質數的同時也給出了相當數量的合數，并不全都是質數。實際上，質數也僅僅只是其中的一部分甚至是一小部分而已。這里，當我們把自然數 代入該公式后，如果得到的 值為整數，我們就說自然數 可以通過“ ”測試。而由此得到的自然數 ，我們則稱之為 “ ”質數。我們也可以將公式 ， 改寫成 ? ，這樣的公式包含了10以內的四個質數：2、3、5、7。至于2x3重復出現了兩次，牽強的解釋可能是由2、3可以構建5和7，因而2、3顯得比5和7更具基礎性一些。

下面由公式 ， 來嘗試尋找200以內的質數。我們先給出由這兩個公式所得到的計算值（這里，n=0、1、2、3……）：

將以上的計算值排列如下：

5 ?7 ?11 13 ?17 ?19 ?23 ?25 ?29 ?31 ?35 ?37 ?41 ?43 ?47 ?49 ?53 ?55 ?59 ?61 ?65 ?67 ?71 ?73 ?77 ?79 ?83 ?85 ?89 ?91 ?95 ?97 ? ? ?101 ?103 ?107 ?109 ?113 ?115 ?119 ?121 ?125 ?127 ?131 ?133 ?137 ?139 ?143 ?145 ?149 ?151 ?155 ?157 ?161 ?163 ?167 ?169 ?173 ?175 ?179 ?181 ?185 ?187 ?191 ?193 ?197 ?199

以上所列出的全部計算值已經包括了200以內的所有質數，當然也還包括一定數量的非質數。如何去掉那些非質數是我們這里要找尋質數的關鍵。我們都知道費馬小定理：如果n是一個質數的話，那么對于任意的一個數 ， 的n次方減去之 后都將是n的倍數。也即 。這樣，我們可以通過應用基于費馬小定理的費馬素性測試，做到去掉上面所列的自然數中的非質數。不過 大都是非常大的數，這給通常的計算及素性測試帶來比較大的麻煩和不便。

本文所給出如下一個比較繁瑣但卻似乎行之有效的方法，也有可能做到去掉上面的非質數，也即我們仿照遠古時候找尋質數的“篩法”：（1）按20以內的已知質數從5開始，按由小到大的順序，先去掉與5 相關的合數：5x5=25，5x7=35，5x11=55，5x13=65，5x17=85，5x19=95（限于100以內的自然數）和進一步的5x23=115，5x25=125，5x29=145，5x31=155，5x35=175，5x37=185（限于200以內的自然數），或者更簡便的就是直接去掉上面所列的計算值中個位數為5的數-------25、35、55、65、85、95和115、125、145、155、175、185;（2）再依次去掉7x7=49，7x11=77，7x13=91（同樣限于100以內的自然數）和7x17=119，7x19=133，7x23=161，7x25=175以及 11x11=121，11x13=143，11x17=187和13x13=169（同樣限于200以內的自然數）。再將這樣的計算值排列如下：

25 ?35 ?49 ?55 ?65 ?77 ?85 ?91 ?95 ?115 ?119 ?121 ?125 ?133 ?143 ?145

155 ?161 ?169 ?175 ?185 ?187

很顯然，上面的值均為非質數，且全都已經包括在前面的計算值中。將前面的計算值中的上述非質數全都去掉，這樣，我們就得到了200以內的除2和3以外的所有質數：

5 ?7 ?11 ?13 ?17 ?19 ?23 ?29 ?31 ?37 ?41 ?43 ?47 ?53 ?59 ?61 ?67 ?71 ?73 ?79 ?83 ?89 ?97 ? ? 101 ?103 ?107 ?109 ?113 ?127 ?131 ?137 ?139 ?149 ?151 157 ?163 ?167 ?173 ?179 ?181 ?191 ?193 ?197 ?199

由上面的討論可知，部分個位數為1、3、7、9的自然數，實際上并不是質數，而是一大類可以通過 “ ”測試的合數，如91、143、187、169，我們暫且將這類仍屬于“ ”質數的自然數稱之為偽質數。通過依次并連續運用上面（1）、（2）那樣的方法，就可以去掉所有類似的非質數（包括偽質數）。這里，我們把建立在公式 和 的基礎上并進一步"篩掉"所有非質數的方法，暫且稱之為"新篩法"-------（a）從5和7的平方開始，之后為5與7相乘以及5和7與所有的“ ”質數依次相乘;（b）從11的平方開始，11再同樣依次和其后所有的“ ”質數依次相乘;其后依次是13、17、19......，再去掉以上所有相應的計算值。通過這樣的"新篩法"，我們就有可能篩掉公式 ， 所帶來的包括偽質數在內的所有的非質數，最終找到我們所要找尋的質數。不難看出，隨著n的增大，一方面給出了真實的質數，同時也給出了越來越多必須被篩掉的非質數，從而導致最終實際存在的質數越來越稀少。

二、贋質數公式

另外一大類不能通過上面的 “ ”測試的自然數，如21、87、117、141、177、561、1023、16383、10234029，其個位數也是1、3、7、9，這和前面的偽質數相同。因其仍然為合數，所以我們暫且稱之為贋質數。贋質數可由兩個連續的“ ” 質數的算術均數中來得到，且所有的贋質數都可以被3整除，也即被稱為贋質數的這類合數都具有最小的質因數3，或者說兩個n值不同但連續的“ ”質數之和都可以被6整除。即：

這也是另外形式的與質數密切相關的計算公式。

相較于其他類似的公式，在n=1、2、3……的情形下，如上面的 ，（這個公式給出的最小的質數為3，）， （其給出的最小的質數為5）以及 （其給出的最小的質數為11）， （其給出的最小的質數也為11）和 ? ?（這兩個公式給出的最小的質數7為和5），還有三百多年前著名的法國業余數學家費馬發現的質數相關公式 ? ? ?（這兩個公式給出的最小的質數為5和7），公式 ， 給出的計算值不但不包括任何偶數（ ? ?這兩個公式的計算值就包含部分偶數），也不包括任何贋質數，且所包含的非質數也是這類公式中最少的。若干個“ ” 質數相乘之后仍能通過“ ”測試（也即這樣的乘積仍是一個偽質數）。

孿生質數（即雙生質數）在公式 ， 中的都具有同一個n值。先“篩掉”與其取相同n值的非質數及質數（或質數及非質數）：如25以及與25取相同n值3的質數23，185以及與185取相同n值30的偽質數187，91以及與91取相同n值14的質數89;再“篩掉”孿生偽質數，如119和121。經過這樣的篩選（也即篩掉所有的非質數以及取同一n值的質數），剩下來的就全都是孿生質數了。

三、計算質數和偽質數以及贋質數的公式 ? （k=0、1、2、3。。。。。。）

從上面我們所探討的還不難看出，對于個位數是1、3、7、9的自然數，似可以分成三大類：質數、能通過“ ”及“ ”測試的偽質數以及不能通過“ ”及“ ”測試的贋質數，偽質數和贋質數本質上都是合數。這里，我們也可以給出包括了質數、偽質數及贋質數的公式 。我們可以先給出100以內的相應計算值：

另外顯而易見是，如果我們說質數是一切數的 “原子”，合數是由若干個質數相乘得到的，那么公式 ? ?（n=1、2、3……）似乎也表明，2和3可能是所有大于等于5的質數的“原子”，也即任意一個大于等于5的質數都是由若干個2和3相加來構成的。還有，5和7出現在前面去掉非質數的"新篩法"中，也即5和7都參與“ ” 質數中的部分非質數的構建，但2和3卻沒有出現前面去掉非質數的"新篩法"中。另外，如果取n=0、1、2、3。。。。。。，則上面的公式 和 ? ?所給出的最小計算值分別為5、7和9。這些似乎都說明了2和3在質數中的基礎性地位和與作用。

以小于20的八個質數尤其是三對孿生質數（5和7、11和13、17和19）為基礎，應用本文以上所給出的尋找質數的"新篩法"，就可以很容易得到100以內的所有質數。在這個新的基礎上似可以找到小于任意一個自然數（比如本文中的200）的所有質數，這至少在原則上來講是可行的和可能的。至于識別任意一個自然數是否為質數或偽質數，我們在這里并不能給出類似基于費馬小定理的費馬素性測試那種簡單有效的方法。我們只知道個位數為0、2、4、5、6、8的自然數及贋質數（其個位數為1、3、7、9）都不是質數。盡管我們在原則上似可以“篩掉”所有的偽質數，但這里并沒有給出能判定任意一個個位數是1、3、7、9的自然數是否為質數或偽質數的簡便方法。

總之，用以上這些只涉及初等數學的想法與方法去探討和對待在自然數中尋找質數這樣的老問題，也許是很有趣的，但這樣的嘗試是否正確和有意義則只能由相關的專家學者去評判了。

參考文獻

[1] ?陳仁政著 ?《說不盡的 》 ?科學出版社 ?2005年

[2] （英）馬庫斯.杜.索托伊著 ?柏華元譯 《悠揚的素數》 人民郵電出版社 2019年