巧用埃拉托色尼篩選法統(tǒng)計大數(shù)據(jù)區(qū)間內(nèi)素數(shù)算法剖析

周靜

摘要：本文從常規(guī)算法出發(fā)找尋并統(tǒng)計素數(shù)，探討了常規(guī)算法在大數(shù)據(jù)區(qū)間找尋并統(tǒng)計素數(shù)的低效問題，引出巧妙運用埃拉托色尼篩選法統(tǒng)計大數(shù)據(jù)區(qū)間范圍內(nèi)素數(shù)個數(shù)方法，并詳細剖析該方法算法思路。

關(guān)鍵詞：素數(shù);埃拉托色尼篩選法;大數(shù)據(jù)區(qū)間;統(tǒng)計

找尋素數(shù)的題目屢見不鮮，總會出現(xiàn)在一些編程教材中。找尋方法都是沿用對素數(shù)判斷規(guī)則，即逐一判斷找尋范圍內(nèi)的數(shù)，在2至其平方根范圍內(nèi)是否存在因子，如果存在就不是素數(shù)，如果不存在就是素數(shù)。這種判斷方法是沿用素數(shù)的定義，也讓初學者能輕松理解并掌握控制流程的好方法。但是當區(qū)間范圍過大以及找尋的數(shù)據(jù)本身也足夠大時，統(tǒng)計速度慢的弊端就會顯現(xiàn)出來，完全體現(xiàn)不了現(xiàn)今信息時代所提倡的高效性，怎么來解決對大數(shù)據(jù)區(qū)間素數(shù)統(tǒng)計問題呢？

1 常規(guī)統(tǒng)計素數(shù)方法的低效問題

對于素數(shù)統(tǒng)計，總會想到先判斷是不是素數(shù)，再執(zhí)行統(tǒng)計。這是思考問題的常規(guī)思路。但是判斷一個數(shù)是不是素數(shù)，所采用常規(guī)判斷素數(shù)方法使用“窮舉法”排除非素數(shù)，窮舉出從2至其平方根中是否存在因子，只要存在則排除。當需要判斷的數(shù)據(jù)過大，使用 “窮舉法”就會變得很低效。

窮舉算法低效在于需要判斷的數(shù)據(jù)可能會在十億至四十多億，需要在2至其平方根（即好幾萬）進行逐一的因子判斷，其耗時比預(yù)想要大得多，且是在一個大區(qū)間內(nèi)統(tǒng)計，需要進行素數(shù)判斷的大數(shù)據(jù)數(shù)量眾多，造成了統(tǒng)計耗時的成倍增長，運行低效問題也更突出。怎樣才能高效實現(xiàn)在大數(shù)據(jù)區(qū)間內(nèi)的素數(shù)統(tǒng)計呢？

2 巧妙統(tǒng)計素數(shù)方法的高效原理

在編程語言（C++）中，正整數(shù)最大范圍可以達到42億多，如果判斷這個數(shù)據(jù)是否是素數(shù)，使用以上常規(guī)判斷不可取的。如果能有一個空間來描述某個范圍內(nèi)哪些是素數(shù)，就可以通過檢索這個空間來統(tǒng)計素數(shù)的數(shù)量。

一個區(qū)間范圍內(nèi)統(tǒng)計素數(shù)只有兩種可能，是或不是，使用C++中的布爾值false和true來表示。定義布爾型數(shù)組：bool prime[60001];用該數(shù)組來描述0-60000范圍內(nèi)哪些是素數(shù)，數(shù)組元素的默認值為false，即假設(shè)其都是素數(shù)，prime數(shù)組初始化如圖1所示：

在0-60000數(shù)字中，對于其中的0和1，已知其不是素數(shù)，所以為數(shù)組元素prime[0]和prime[1]賦值true，表示其不是素數(shù)，如圖2所示。

從數(shù)字2開始判斷其是素數(shù)，但后面所有是2倍數(shù)的數(shù)就都不是素數(shù)，為其賦值true，這就是埃拉托色尼篩選法的中心思想，算法實現(xiàn)：

for（long i=2;i<=60000;i++）

if（！prime[i]） {

for（long j=i+i;j<=60000;j=j+i）

prime[j]=true;

}

通過以上代碼的執(zhí)行，在prime數(shù)組中就記錄0至60000哪些是素數(shù)（值為false就是素數(shù)）的信息。prime數(shù)組的表示如圖3所示：

這種方法可以將60000內(nèi)所有非素數(shù)置true，是因為只要不是素數(shù)就會存在因子，其因子如果也不是素數(shù)，可以繼續(xù)分解，總之一個非素數(shù)都可以表達成比它小的素數(shù)乘積，即是素數(shù)倍數(shù)，既然是素數(shù)倍數(shù)，根據(jù)前面的說法，就應(yīng)該為其賦值為true，標識出其不是素數(shù)了。

其高效體現(xiàn)在代碼中進入內(nèi)循環(huán)存在條件，且內(nèi)循環(huán)次數(shù)隨i值的遞增，將成i倍遞減，與逐一判斷是否存在因子的素數(shù)判斷作為內(nèi)循環(huán)的效率是不可相提并論的。

對大數(shù)據(jù)區(qū)間素數(shù)統(tǒng)計該怎么實現(xiàn)呢？在實現(xiàn)代碼中使用了prime數(shù)組存儲布爾值來描述0-60000中哪些是素數(shù)。定義數(shù)組大小為60000的原因是因為描述素數(shù)范圍最大數(shù)是42億多，取其平方根是60000多，當?shù)玫?0000以內(nèi)的所有素數(shù)，再以這些素數(shù)為基礎(chǔ)，將需要描述的大數(shù)據(jù)范圍內(nèi)素數(shù)倍數(shù)都賦值為true，素數(shù)統(tǒng)計工作就只需要單層循環(huán)檢索即可實現(xiàn)。

注意需要了解找尋的大數(shù)據(jù)范圍數(shù)量，才能設(shè)計一個空間來描述這些數(shù)中哪些是素數(shù)?？梢灶A(yù)想一下需要判斷的區(qū)間范圍，假如是1，000，000，那么需要設(shè)計1，000，000的空間來描述該范圍內(nèi)數(shù)據(jù)是否是素數(shù)。即：bool primeMax[1000001];該數(shù)組就用來描述這個大數(shù)據(jù)范圍內(nèi)的數(shù)哪些是素數(shù)。

描述的數(shù)據(jù)范圍有3種情況：

第一種是當描述數(shù)據(jù)都在60000以內(nèi);

第二種需要描述的數(shù)據(jù)一部分在60000以內(nèi)，一部分在60000以外;

第三種是需要描述的數(shù)據(jù)都在60000以外;

這里用整型變量left表示范圍左邊界值，用整型變量right表示右邊界值，用整型變量count且初始化值為0來累加統(tǒng)計素數(shù)量。

（1）第一種情況的統(tǒng)計處理

if（right<=60000）{

for（long i=left;i<=right;i++）

if（！prime[i]）count++;

cout<

}

直接利用prime數(shù)組統(tǒng)計完需要描述的區(qū)間范圍內(nèi)的素數(shù)個數(shù)并輸出;

（2）第二種情況的統(tǒng)計處理

需要分段處理，首先處理在60000以內(nèi)的數(shù)據(jù)，這些數(shù)據(jù)按第一種情況處理;其次處理不在60000以內(nèi)的數(shù)據(jù)，這些數(shù)據(jù)可以按第三種情況處理。

① 第一段數(shù)據(jù)（在60000以內(nèi)的數(shù)據(jù)）統(tǒng)計處理。

if（left<=60000）{

for（long i=left;i<=60000;i++）

if（！prime[i]）count++;

left=60001;

}

② 第二段數(shù)據(jù)（在60000以外的數(shù)據(jù)）統(tǒng)計處理

上面第一段數(shù)據(jù)統(tǒng)計處理代碼實現(xiàn)最后一條語句將60001賦值給left，作用是改變左邊界值。這樣使得第二段數(shù)據(jù)可以按下面第三種情況統(tǒng)計處理。

（3）第三種情況的統(tǒng)計處理

需要使用上面定義的primeMax數(shù)組來標識60000以外數(shù)據(jù)是否是素數(shù)，該數(shù)組如圖4所示：

與prime數(shù)組類似，先假設(shè)所描述60000以外數(shù)據(jù)它們?nèi)慷际撬財?shù)，再通過檢索prime數(shù)組中的素數(shù)，標識需要描述的60000以外的區(qū)間內(nèi)哪些是素數(shù)，為其賦值為true。

其代碼實現(xiàn)如下：

long temp;

for（long i=2;i<=60000;i++）{

if（！prime[i]）{

for（unsigned long j=left/i;j<=right/i;j++） {

temp=j*i-left;

if（temp>=0）primeMax[temp]=true;

}

}

}

對于代碼中的left/i和right/i作用是使得內(nèi)循環(huán)次數(shù)成i倍遞減表示方法。因為要為素數(shù)的倍數(shù)置true，表示其不是素數(shù)。

prime中描述了所有60000以內(nèi)的素數(shù)，將在給出的大數(shù)據(jù)范圍內(nèi)標識出是prime數(shù)組中素數(shù)倍數(shù)的數(shù)，將這個表示存儲在primeMax數(shù)組中。例如，描述60001-70001范圍;當i=2時;primeMax數(shù)組的表示如圖5所示：

代碼中需要置true的primeMax數(shù)組元素下標temp=j*i-left;該表達式j(luò)*i代表需要描述的大數(shù)據(jù)，該數(shù)據(jù)是i的倍數(shù)。減去left將該數(shù)對應(yīng)到primeMax數(shù)組中相應(yīng)的元素上;

在為primeMax數(shù)組元素賦值true時，有一個if條件語句，需要判斷temp是否大于等于0，該判斷的作用是看描述的大數(shù)據(jù)j*i，是否在需要描述數(shù)據(jù)區(qū)間范圍內(nèi);如果temp小于零，代表j*i小于left左邊界，即不用描述該數(shù)據(jù)。當標識完prime數(shù)組中所有素數(shù)在大數(shù)據(jù)區(qū)間內(nèi)的倍數(shù)標識，即為primeMax數(shù)組賦值后，就可以實現(xiàn)區(qū)間類素數(shù)統(tǒng)計了;前面已經(jīng)實現(xiàn)了用檢索prime數(shù)組對60000以內(nèi)素數(shù)統(tǒng)計，現(xiàn)在就對primeMax數(shù)組進行檢索，統(tǒng)計60000以外的素數(shù)量，其實現(xiàn)代碼是：

for（long i=0;i<=right-left;i++）

if（！primeMax[i]）count++;

cout<

前面詳細講解利用埃拉托色尼篩選法巧妙統(tǒng)計大數(shù)據(jù)區(qū)間內(nèi)素數(shù)，希望大家能理解和掌握該方法，并能靈活借鑒該方法解決其他類似的問題。

基金項目：本文系2018-2019年度工業(yè)和信息化職業(yè)教育教學科研課題 “藍橋杯”技能大賽成果資源在高職教育教學中的實踐與應(yīng)用（編號GS-2019-10-02）; 重慶電子工程職業(yè)學院卓越技術(shù)技能人才工匠工坊項目“千貝軟件工匠工坊”（編號：0319010225 ）的研究成果。

（作者單位：重慶電子工程職業(yè)學院）