求素數(shù)新法

李 高，常秀芳

（山西大同大學數(shù)學與統(tǒng)計學院，山西大同 037009）

對整數(shù)性質的研究開始很早，對數(shù)的性質的研究也越來越深入和精細，并逐漸形成了數(shù)學的一個分支—數(shù)論。

定義1對于一個整數(shù)只有1 和本身是它的約數(shù)，則該整數(shù)稱為質數(shù)或素數(shù)。

素數(shù)盡管耳熟能詳，它的出現(xiàn)使一個個貌似簡單的問題，如算術基本定理、素數(shù)定理、素數(shù)等差數(shù)列、哥德巴赫猜想、黎曼猜想、孿生質數(shù)猜想[1-2]等，多少代數(shù)學家一身追尋與探索，且一直困惑著，而終身無果。

早在公元前六世紀,古希臘的數(shù)學家畢達哥拉斯和他的學生就研究了數(shù)的整除性問題。公元前三世紀，歐幾里得就提出了用輾轉相除法求最大公約數(shù)的方法。我國在整數(shù)性質方面的研究也比較早，約在公元前100 年到公元100 年間成書的《九章算術》里講到約分，方法是“可半者半之,不可半者，副置分母、子之數(shù)，以少減多，更相減損，求共等也，以等數(shù)約之[3]?！边@就是說分子、分母都是偶數(shù)時，應該都用2去除；如果不都是偶數(shù)，那么用輾轉相減的方法，從較大的數(shù)里減去較小的數(shù),最后得到一個余數(shù)和減數(shù)相等,這就是所求的最大公約數(shù)，這種輾轉相減求最大公約數(shù)的方法和歐幾里德算法異曲同工,理論上是完全一致的。

1 素數(shù)的無窮性

素數(shù)的獨特形式吸引著眾多數(shù)學家們，關于素數(shù)有無窮多個的問題，早在公元前300 多年，就被古希臘數(shù)學家歐幾里德在《幾何原本》中證明。但是，由于數(shù)越大，發(fā)現(xiàn)素數(shù)就越困難。因此，目前人類已知的素數(shù)還是為數(shù)有限的。

17 世紀法國費爾馬(Pierrede Fermat)曾經(jīng)猜測形如22n+1(n＞0)的數(shù)都是素數(shù)[4]，其實這個猜測是錯誤的，例如，當n=5 時，25+1=4 294 967 297=641×6 700 417 并不是素數(shù)，但是費爾馬的猜測卻給了后人很大的啟發(fā)，以后發(fā)現(xiàn)的大素數(shù)都與這個公式相近。1876 年數(shù)學家盧卡斯發(fā)現(xiàn)了當時最大的素數(shù)是2127-1 是37 位數(shù)，這個紀錄保持了75 年，直到1951 年，由于計算機的問世，才發(fā)現(xiàn)了更大的具有7個數(shù)位素數(shù)180×(2127-1)2+1 。此后，紀錄不斷被刷新，1979 年美國勞倫斯·利莫費爾實驗室的兩位計算機專家發(fā)現(xiàn)了目前最大的素數(shù)244497-1，這個數(shù)是1 395位數(shù)。

17 世紀法國數(shù)學家馬林·梅森(Mersenne Primes)猜測形如2P-1 的正整數(shù)都是素數(shù)(其中P是素數(shù))。若2P-1是素數(shù)，則稱為梅森素數(shù)，簡稱梅森數(shù)。當P=2,3,5,7 時，都是素數(shù)，但P=11 時，211-1=2047=23×89不是素數(shù)，是否存在無窮多個梅森素數(shù)是數(shù)論中未解決的難題之一[4]。

2016年1月美國柯蒂斯·庫珀(Curtis Cooper)發(fā)現(xiàn)世界上迄今為止最大的梅森質數(shù)257885161-1，長達2 233萬位，如果用普通字號將它打印出來長度將超過65 km。至今累計發(fā)現(xiàn)49 個梅森素數(shù)，尋找梅森質數(shù)的同時，對其重要性質—分布規(guī)律的研究也一直在進行著。英、法、德、美等國的數(shù)學家都曾分別給出過有關梅森質數(shù)分布的猜測，但都以近似表達式給出，與實際情況的接近程度均難如人意。中國數(shù)學家、語言學家周海中是這方面研究的領先者，于1992 年首次給出了梅森質數(shù)分布的精確表達式。這一成果后來被國際上命名為“周氏猜想”。

素數(shù)貌似簡單，但研究難度卻極大。由于梅森素數(shù)珍奇而迷人，被人們譽為“數(shù)論中的鉆石”。這種素數(shù)歷來是數(shù)論研究的一項重要內(nèi)容，眾多科學家認為梅森素數(shù)的研究成果是一個國家科技水平的體現(xiàn)，不僅推動了數(shù)論的研究，而且促進了計算機技術、程序設計等技術的發(fā)展。一些素數(shù)已經(jīng)被用于加密和其他實際應用任務，因此成為當今科學探索的熱點和難點之一。威斯康辛州立大學（University of Wisconsin）的數(shù)學家Jordan Ellenberg 就曾說：“發(fā)現(xiàn)一個梅森素數(shù)就像是在干草堆里找一根針那么困難。這項發(fā)現(xiàn)在計算機工程領域的價值要遠大于數(shù)學領域的價值?！?/p>

2 埃拉托斯特尼篩

2.1 埃拉托斯特尼篩法

最初的若干素數(shù)為2，3，5，7，11，13，17，19，23，29，31，37，41，43，…，如果不太大，求小于的素數(shù)并非難之事。

公元前三世紀，希臘學者埃拉托斯特尼(Eratosthenes)找到一種求1 000以內(nèi)質數(shù)的方法。依次寫出2 到1 000 的自然數(shù)，第一個數(shù)2 是質數(shù)，把2 留下，把所有2 的倍數(shù)即偶數(shù)劃去；2 后面第一個未劃去的數(shù)是3，而3 是質數(shù)，把它留下再把剩下的數(shù)中所有3 的倍數(shù)都劃去；3 后面第一個未劃去的數(shù)是5，而5 是質數(shù)，把它留下，再把剩下的數(shù)中所有5的倍數(shù)都劃去。這樣繼續(xù)下去劃到37 以前的一個質數(shù)為止，最后留下的數(shù)就組成了1 000 以內(nèi)的質數(shù)表。此法稱為求素數(shù)的埃拉托斯特尼篩法。

2.2 埃拉托斯特尼篩由來

因為希臘人是把數(shù)寫在涂臘的板上,每要劃去一個數(shù),就在上面記以小點,尋求質數(shù)的工作完畢后,這許多小點就象一個篩子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩”,簡稱“篩法”。

另一種解釋是當時的數(shù)寫在紙草上,每要劃去一個數(shù)，就把這個數(shù)挖去，尋求質數(shù)的工作完畢后，這有許多孔的紙草就象一個篩子。

2.3 判斷一個正整數(shù)是素數(shù)的方法

一個正整數(shù)N是否為素數(shù)，最簡單的方法就是試除法，將該數(shù)N用小于等于的所有素數(shù)去試除，若均無法整除，則N為素數(shù)。

證明：利用反證法，假設這樣篩出來的N是合數(shù)，且不能被小于等于其平方根的所有素數(shù)整除，那么N一定能被大于其平方根小于其本身的某個素數(shù)整除N，記該素數(shù)為M。則，且存在正整數(shù)K，使得N=MK，于是。若K為素數(shù)，則與前面假設矛盾；若K為合數(shù)，則存在另一素數(shù)整除K，當然也整除N，于是也與前面假設矛盾?？傊?，不論何種情形，這樣的N不能是合數(shù)只能是素數(shù)。

3 一種新的求素數(shù)的方法

如果N較大，遵照埃拉托斯特尼篩法需要劃到以前的一個質數(shù)為止，即得小于N的所有素數(shù),直到目前為止，都是用埃拉托斯特尼篩法或其法略加變化而得出的。由于N較大時，該法非常麻煩?，F(xiàn)給出一種新的求素數(shù)的方法，是從素數(shù)3，5 出發(fā),遂步地、無限地遵循下面方法進行就能陸續(xù)地求出所有的素數(shù)。具體方法如下：

第1 步：首先素數(shù)3 自乘得9，則5 和9 之間的奇數(shù)7必為素數(shù)。

因為,如果5 和9 之間的奇數(shù)7 不是素數(shù)的話，那么就應該有比5和3還小的素數(shù)自乘或3，5相乘的積中包含7，但這樣的素數(shù)顯然是不存在的，故5 和9 之間的奇數(shù)7 必為素數(shù)。因此，比9 小的所有素數(shù)3，5，7已求得。

第2步：求比9大的素數(shù)。

在3，5，7 的自乘或互乘的乘積中,比9 大的最小數(shù)是3×5=15,則9 和15 間的奇數(shù)11，13 必為素數(shù)。因此，比15小的所有素數(shù)2，3，5，7，11，13已求得。

第3步：求比15大的素數(shù)。

在3，5，7，11，13的自乘或互乘的乘積中,比15大的最小數(shù)是3×7=21，則15 和21 之間的奇數(shù)17，19 必為素數(shù)，因此，比21 小的所有素數(shù)2，3，5，7，11，13，17，19已求得。

第4步：求比21大的素數(shù)。

在3，5，7，11，13，17，19 的自乘或互乘的乘積中,比21大的最小數(shù)是,于是21和25之間的奇數(shù)23必為素數(shù)。又是緊挨著25 的奇數(shù),比25 小的素數(shù),當然比27 小的素數(shù)也就求得了，即比27 小的所有素數(shù)2，3，5，7，11，13，17，19，23已求得。

第5步：求比27大的素數(shù)。

在3，5，7，11，13，17，19，23的自乘或互乘的乘積中,比27 大的最小數(shù)是3×11=33，于是27 和33 之間的奇數(shù)29、31 必為素數(shù)。因此，比33 小的所有素數(shù)2、3，5，7，11，13，17，19，23，29，31已求得。

…

繼續(xù)不斷地照此進行下去,就能一個不漏地求得越來越大的素數(shù)。

這個過程可無限進行下去，其過程見圖1。

圖1 求素數(shù)新法圖

4 結語

遵照無限地遵循分層推進的方法，從奇素數(shù)3，5開始，利用自乘或互乘的原理，在乘積中,分別比數(shù)9，15，21，27，33，…，大的最小數(shù)間的奇數(shù)必為素數(shù)，即可求出所有的素數(shù)。這種求素數(shù)的方法撇棄了最原始的埃拉托斯特尼篩法，得到了一種新的求素數(shù)的方法。該方法不僅可以簡便地求得任意一個素數(shù)，而且更容易編程在計算機上的應用。