素?cái)?shù)篩選算法的一種改進(jìn)

姚凱哲 呂雅文 許天啟 童堯

摘要：本文對傳統(tǒng)的素?cái)?shù)篩選算法的缺點(diǎn)進(jìn)行了分析和改進(jìn)。并在埃拉托斯特尼篩法（sieve of Eratosthenes）的基礎(chǔ)之上，設(shè)計(jì)了一種基于已知素?cái)?shù)來尋找未知素?cái)?shù)的區(qū)間篩法。區(qū)間篩法突破了由計(jì)算機(jī)內(nèi)存分配造成的數(shù)量級限制，大幅提升了尋找素?cái)?shù)的范圍，并通過優(yōu)化篩選過程提升了算法運(yùn)行速度。實(shí)驗(yàn)結(jié)果表明，經(jīng)過改進(jìn)的區(qū)間篩法在篩選范圍上遠(yuǎn)大于傳統(tǒng)篩法，并且具有較好的時間復(fù)雜度。

關(guān)鍵詞：素?cái)?shù)；篩法；區(qū)間篩法；篩選范圍

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）17-0075-02

1 引言

素?cái)?shù)，是數(shù)論中最古老、最基本但至今仍受到廣泛關(guān)注的話題之一。圍繞著素?cái)?shù)產(chǎn)生了一系列世界級的難題，吸引了歷史上一大批著名的數(shù)學(xué)家參與其中，其中有很多問題至今仍未解決。篩法是尋找素?cái)?shù)的一種常見而又高效的方法。尋找與判別素?cái)?shù)的算法在現(xiàn)代信息科學(xué)與程序設(shè)計(jì)中起著相當(dāng)重要的作用。

2 經(jīng)典的素?cái)?shù)篩選法

2.1 埃拉托斯特尼篩法

埃拉托斯特尼篩法（sieve of Eratosthenes）簡稱埃氏篩或愛氏篩， 是一種由埃及數(shù)學(xué)家埃拉托斯特尼所提出的一種簡單檢定素?cái)?shù)的算法。他的方法是：先將2～[n]從小到大排列。選中2，然后將2的其他倍數(shù)篩去；再選中下一個未被篩去的數(shù)3，將3的其他倍數(shù)都篩去；下一個未被篩除的數(shù)是5，將5的其他倍數(shù)篩去……以此類推，一直到?jīng)]有數(shù)可以被選擇為止，剩下未被篩除的數(shù)即為2～[n]中的所有素?cái)?shù)。埃氏篩法原理簡單，實(shí)現(xiàn)起來比較容易。它的算法復(fù)雜度為[O（nloglogn）]。

2.2 線性篩法——?dú)W拉篩法

埃氏篩法雖然原理簡單，速度較快，但是篩選過程中任意一個合數(shù)都會被它的[k]個素因子處[k]理次，造成大量不必要的計(jì)算。因此，歐拉篩法就是對這點(diǎn)不足的改進(jìn)。對于從2開始的每個自然數(shù)[i]，先將每個發(fā)現(xiàn)的素?cái)?shù)歸入集合[P]中，然后將集合[P]中的每一個素?cái)?shù)的[i]倍篩去。當(dāng)[i]被[P]中某個素?cái)?shù)整除時，便立即進(jìn)入下一輪篩選，直到所有[n]以內(nèi)的數(shù)都被處理過為止。這時，[P]中就包含了[n]以內(nèi)的所有素?cái)?shù)。這種算法保證了每一個合數(shù)都只被自己的最小素因子處理一次，大幅減少了多余的運(yùn)算，提高了運(yùn)算效率。歐拉篩法的時間復(fù)雜度為[O（n）]，因此又被稱為線性篩法。

2.3 傳統(tǒng)篩法的不足之處

在傳統(tǒng)篩法算法中，獲取[n]以內(nèi)的素?cái)?shù)需要消耗與[n]等量大小的內(nèi)存。這導(dǎo)致[n]過大時，計(jì)算機(jī)無法提供足夠的內(nèi)存，導(dǎo)致程序崩潰。傳統(tǒng)篩法的另一個缺點(diǎn)是只能一次性獲取2～[n]之間的素?cái)?shù)，而不能僅僅獲取任一個區(qū)間內(nèi)素?cái)?shù)。若只要求某一區(qū)間內(nèi)的素?cái)?shù)則會造成程序在運(yùn)行時大量不必要的內(nèi)存消耗，并且極大地限制了區(qū)間的可行范圍。

3 篩法的改進(jìn)

對于傳統(tǒng)篩法的上述缺點(diǎn)，本文提出了分區(qū)間篩選的思想并對算法的以下幾處進(jìn)行改進(jìn)優(yōu)化，使得通過篩法可以獲得更大范圍內(nèi)的素?cái)?shù)，并且不受起始數(shù)的限制。

3.1 使用已知素?cái)?shù)進(jìn)行篩選

定理1 若[n≥2]是合數(shù)，則必有質(zhì)數(shù)[p|n]，[p≤n].

通過算數(shù)基本定理可知，每個合數(shù)都可以分解成若干個素?cái)?shù)的乘積，因此只要驗(yàn)證一個數(shù)是否被某個素?cái)?shù)整除就可以判斷它是否為合數(shù)，這是就篩法的基本思想。根據(jù)定理1，該數(shù)的最小的素因子不會超過它的平方根。因此，若現(xiàn)在已知前2～[n]范圍內(nèi)素?cái)?shù)，則通過遍歷一次整個素?cái)?shù)集合可以快速計(jì)算出[n2]以內(nèi)全部的素?cái)?shù)。

3.2 分區(qū)間篩選

傳統(tǒng)篩法尋找素?cái)?shù)時，由于沒有任何已知素?cái)?shù)，因此需要從第一個素?cái)?shù)2開始計(jì)算，篩選序列的構(gòu)造也必須從2開始，很大程度上限制了篩選的范圍。由之前的討論可知，若已知2～[n]范圍內(nèi)素?cái)?shù)，則可以對篩法算法進(jìn)行適當(dāng)?shù)母倪M(jìn)，從而獲得[n2]以內(nèi)任一區(qū)間里的素?cái)?shù)。這種方法有效的擺脫了傳統(tǒng)篩法對篩選起點(diǎn)的限制。

圖1展示了區(qū)間篩法的計(jì)算過程。其中[n]以內(nèi)的素?cái)?shù)集可以通過傳統(tǒng)篩法程序事先得到。由于線性篩法的算法原理在分區(qū)間的篩法上并不適用，因此這里使用了埃氏篩法的算法原理進(jìn)行篩選。對于區(qū)間[[m，n]]，需使用[n]內(nèi)的素?cái)?shù)進(jìn)行篩選，所以該算法的時間復(fù)雜度為[O（（n-m）loglogn）]，比埃氏篩法的復(fù)雜度稍低一些。

3.3 區(qū)間篩法的優(yōu)化

對于區(qū)間篩法，在實(shí)際的編程中還可以對以下幾部分進(jìn)行優(yōu)化，以加快速度并減少空間占用率。

3.3.1 去偶存奇

除2以外的偶數(shù)都不是素?cái)?shù)，因此在篩選時可以直接略去偶數(shù)，只考慮奇數(shù)。對篩選數(shù)組的相應(yīng)下標(biāo)做映射[S]：[n→2n+1]，在判定時通過做逆映射修改相應(yīng)下標(biāo)的值來完成篩選，這樣做使篩選數(shù)組的大小比原來縮小了一倍。去偶操作不僅降低了程序的內(nèi)存占用率，同時省去對偶數(shù)的篩除也提高了算法的效率。

3.3.2 優(yōu)化篩選因數(shù)范圍

在計(jì)算過程中，調(diào)整篩選因數(shù)的取值范圍可以去除冗余的運(yùn)算。篩法算法的具體實(shí)現(xiàn)里通過將素?cái)?shù)[p]與另一數(shù)[i∈Ip]相乘來篩除素因子為[p]的合數(shù)，這里[Ip]表示所有與[p]相乘的因數(shù)的集合。由于是在某一區(qū)間中篩選素?cái)?shù)，所以當(dāng)[p]改變時，集合[Ip]中的元素也會相應(yīng)的改變，[i]的取值范圍隨著[p]的增大而減小。事實(shí)上，若要篩去區(qū)間[[m，n]]中素因子為[p]的偶數(shù)，則因子[i]只需取[[m/p]+1]到[[n/p]+1]之間的所有奇數(shù)即可。

定理2 當(dāng)[Ip]中最存在小于[p]的因數(shù)時，可以將[Ip]中小于[p]的元素去除。

證明：[?i∈][Ip]滿足[i

根據(jù)定理2，在設(shè)計(jì)算法時對[Ip]的范圍做適當(dāng)?shù)恼{(diào)整，可以防止一部分?jǐn)?shù)被重復(fù)篩選。

綜合上述兩處對算法優(yōu)化，用C++實(shí)現(xiàn)的核心代碼如下：（對區(qū)間[[M，N]]篩選）

3.4 擴(kuò)大篩選范圍

運(yùn)用區(qū)間篩法，通過對較大的區(qū)間進(jìn)行合理的劃分并迭代計(jì)算可以大幅擴(kuò)大篩選的范圍。并且可以將每一次新的篩選結(jié)果存入素?cái)?shù)集中，擴(kuò)大的素?cái)?shù)集將為更大數(shù)量級的篩選提供保證。

圖2展示了在大區(qū)間內(nèi)篩選素?cái)?shù)的基本過程。例如需要計(jì)算1000億以內(nèi)的素?cái)?shù)。假設(shè)程序一次最多只能在10億大小的區(qū)間篩選，則可以將1000億的區(qū)間以10億大小等分為100個子區(qū)間。首先用線性篩法獲得2～10億內(nèi)的素?cái)?shù)集并保存，然后用區(qū)間篩法對之后的每個子區(qū)間進(jìn)行計(jì)算，每輪計(jì)算完成后將結(jié)果添加到已有的素?cái)?shù)集中，為以后的篩選提供素?cái)?shù)。經(jīng)過反復(fù)迭代即可獲得1000億以內(nèi)的素?cái)?shù)集。

事實(shí)上，只要預(yù)先輸入一小部分從3開始的素?cái)?shù)，該算法就能通過合理的分配篩選區(qū)間迭代計(jì)算出任意規(guī)模大小內(nèi)的所有素?cái)?shù)，打破了傳統(tǒng)篩法對空間上的限制。

4 實(shí)驗(yàn)結(jié)果分析

本文使用C++實(shí)現(xiàn)了三種算法，并且分別選取了1億，5億，10億的區(qū)間來測試它們尋找素?cái)?shù)所需的內(nèi)循環(huán)次數(shù)，具體結(jié)果如圖3所示：

可以看到，經(jīng)過優(yōu)化的區(qū)間篩法循環(huán)次數(shù)已經(jīng)十分接近線性的歐拉篩法，與原始的埃氏篩法相比有很大的改進(jìn)。

同時還給出了三種算法在實(shí)際程序運(yùn)行中最大的可篩選素?cái)?shù)范圍，結(jié)果見表1：

5 結(jié)語

傳統(tǒng)的埃氏篩法與歐拉篩法可以在短時間里快速地尋找出素?cái)?shù)，但在范圍上受到了限制。區(qū)間篩法通過使用已經(jīng)得到的素?cái)?shù)集在某個區(qū)間內(nèi)尋找新的素?cái)?shù)，同時在奇偶判定、縮小篩選因數(shù)范圍兩方面對算法進(jìn)行優(yōu)化，突破了傳統(tǒng)的篩法在范圍上的局限。通過將傳統(tǒng)篩法與區(qū)間篩法相結(jié)合并合理劃分區(qū)間，可以大幅提升篩選素?cái)?shù)的范圍。

參考文獻(xiàn)：

[1] 閔嗣鶴，嚴(yán)士鍵.初等數(shù)論[M].第三版.高等教育版社，2003，12：14-18.

[2] 司釗，司琳.哥德巴赫猜想與優(yōu)化篩法[M].西北工業(yè)大學(xué)出版社，2005，9：10-14.

[3] 葉煜，周洪林，任華.素?cái)?shù)篩選法的改進(jìn)及C語言實(shí)現(xiàn)[J].計(jì)算機(jī)與數(shù)字工程，2013，6：899-900.

[4] 高曉巍，鄭大釗.查找素?cái)?shù)的有效方法及在計(jì)算機(jī)上的實(shí)現(xiàn)[J].高師理科學(xué)刊，2005，8：9-12.