李 高，史萬紅

(1.山西大同大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，山西 大同 037007；2.尚義縣紅土梁鎮(zhèn)中心小學(xué)，河北 尚義 075760)

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

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

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

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

1 素數(shù)的無窮性

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

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

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

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

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

2 埃拉托斯特尼篩

2.1 埃拉托斯特尼篩法

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

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

2.2 埃拉托斯特尼篩由來

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

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

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

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

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

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

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

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

第三步：求比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已求得。

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

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

第五步：求比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ù)不斷地照此進(jìn)行下去,就能一個不漏地求得越來越大的素數(shù)。

這個過程可無限進(jìn)行下去，其過程如下