周靜

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

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

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

1 常規(guī)統(tǒng)計(jì)素?cái)?shù)方法的低效問(wèn)題

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

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

2 巧妙統(tǒng)計(jì)素?cái)?shù)方法的高效原理

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

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

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

從數(shù)字2開(kāi)始判斷其是素?cái)?shù)，但后面所有是2倍數(shù)的數(shù)就都不是素?cái)?shù)，為其賦值true，這就是埃拉托色尼篩選法的中心思想，算法實(shí)現(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;

}

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

這種方法可以將60000內(nèi)所有非素?cái)?shù)置true，是因?yàn)橹灰皇撬財(cái)?shù)就會(huì)存在因子，其因子如果也不是素?cái)?shù)，可以繼續(xù)分解，總之一個(gè)非素?cái)?shù)都可以表達(dá)成比它小的素?cái)?shù)乘積，即是素?cái)?shù)倍數(shù)，既然是素?cái)?shù)倍數(shù)，根據(jù)前面的說(shuō)法，就應(yīng)該為其賦值為true，標(biāo)識(shí)出其不是素?cái)?shù)了。

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

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

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

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

第一種是當(dāng)描述數(shù)據(jù)都在60000以?xún)?nèi);

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

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

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

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

if（right<=60000）{

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

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

cout<

}

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

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

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

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

if（left<=60000）{

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

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

left=60001;

}

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

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

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

需要使用上面定義的primeMax數(shù)組來(lái)標(biāo)識(shí)60000以外數(shù)據(jù)是否是素?cái)?shù)，該數(shù)組如圖4所示：

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

其代碼實(shí)現(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;

}

}

}

對(duì)于代碼中的left/i和right/i作用是使得內(nèi)循環(huán)次數(shù)成i倍遞減表示方法。因?yàn)橐獮樗財(cái)?shù)的倍數(shù)置true，表示其不是素?cái)?shù)。

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

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

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

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

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

cout<

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

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

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