張國欽， 宋 偉， 馬俊興

(河南財政金融學(xué)院(龍子湖校區(qū)) 現(xiàn)代教育技術(shù)中心，河南 鄭州 450046)

素數(shù)篩選法的實(shí)現(xiàn)及優(yōu)化

張國欽， 宋 偉， 馬俊興

(河南財政金融學(xué)院(龍子湖校區(qū)) 現(xiàn)代教育技術(shù)中心，河南 鄭州 450046)

根據(jù)素數(shù)篩選法的思想設(shè)計(jì)了一種算法，并對該算法進(jìn)行了優(yōu)化.對得到的算法進(jìn)行了時間復(fù)雜度分析，并從平均運(yùn)行時間和主要代碼執(zhí)行次數(shù)兩個指標(biāo)對算法進(jìn)行度量.測試結(jié)果表明，優(yōu)化后的算法具有較高的執(zhí)行效率.

素數(shù)；篩選法；優(yōu)化；時間復(fù)雜度；執(zhí)行效率

0 引言

素數(shù)是指大于1并且只能被1和自身整除的自然數(shù).素數(shù)在計(jì)算機(jī)中有著廣泛的應(yīng)用，比如用于密碼設(shè)計(jì)領(lǐng)域的大素數(shù)，其原理是：將一個很大的數(shù)分解成若干素數(shù)的乘積非常困難，但將幾個素數(shù)相乘卻相對容易得多.在這種密碼設(shè)計(jì)中，需要使用較大的素數(shù)，素數(shù)越大，密碼被破譯的可能性就越小.判斷一個整數(shù)是否素數(shù)的一種簡便方法是試除法[1]，求一個整數(shù)n范圍內(nèi)的所有素數(shù)的常用方法是古希臘數(shù)學(xué)家埃拉托色尼所發(fā)明的素數(shù)篩法[2-3].

1 素數(shù)的判斷方法

1.1 基本試除法

根據(jù)素數(shù)的定義，判斷一個自然數(shù)n是否為素數(shù)，可以用2～n-1之間的自然數(shù)i來除n，如果n能被i整除，則n是合數(shù)，否則n是素數(shù).

1.2 改進(jìn)的試除法

2 篩選法求素數(shù)的算法及優(yōu)化

2.1 篩選法求素數(shù)的算法思想

素數(shù)篩選法的基本思想是把一定范圍內(nèi)的自然數(shù)中不是素數(shù)的數(shù)劃去，剩下的就是素數(shù).依據(jù)是自然數(shù)中除了1之外，不是素數(shù)，就是合數(shù).篩選法求素數(shù)的過程描述如下：把不超過N的所有自然數(shù)按從小到大的順序排列起來；1既不是素數(shù)，也不是合數(shù)，劃去；2是素數(shù)，把2留下，再把2后面所有能被2整除的數(shù)都劃去；2后面第一個沒劃去的數(shù)是3，把3留下，再把3后面所有能被3整除的數(shù)都劃去；3后面第一個沒劃去的數(shù)是5，把5留下，再把5后面所有能被5整除的數(shù)都劃去；這樣一直做下去，就會把不超過N的全部合數(shù)都篩掉，留下的就是不超過N的全部素數(shù).

2.2 算法實(shí)現(xiàn)及優(yōu)化

1 #include

2 #include

3 #include

4 #define N 250000

5 int main()

6 {static int a[N+1];

7 int i,j,n=0,RepeatTimes=0;

8 long start,end;

9 start=clock();

10 for (i=1;i<=N;i++)

11 a[i]=i;

12 for (i=2;i<=sqrt(N);i++)

13 for (j=i+1;j<=N;j++)

14 {if(a[i]!=0 && a[j]!=0)

15 if (a[j]%a[i]==0)

16 a[j]=0;

17 RepeatTimes++; }

18 end=clock();

19 printf(" 求素數(shù)所用時間:time=%.3lf秒 ",(double)(end-start)/CLOCKS_PER_SEC);

20 printf("求素數(shù)執(zhí)行循環(huán)次數(shù):%d ",RepeatTimes);

21 //輸出素數(shù)的代碼，不是算法的主要部分，略去；

28 return 0; }

在算法a中加入了執(zhí)行時間和循環(huán)次數(shù)等直觀表示算法執(zhí)行效率的度量指標(biāo).該算法可以進(jìn)一步優(yōu)化.行12的語句中函數(shù)調(diào)用sqrt(N)作為條件表達(dá)式的一部分，每次判斷都要用到，因此可以把該值放在for語句之前計(jì)算出來以備調(diào)用(雖然編譯器可以對此進(jìn)行優(yōu)化，但是我們不應(yīng)該把過多的工作交給編譯器去做).行14中的判斷條件if(a[i]!=0 && a[j]!=0)放的位置不合適，因?yàn)槿绻鸻[i]==0即i為合數(shù)，那么i后面所有能整除i的數(shù)已經(jīng)被劃去了.在算法a中行8和行9之間插入“int k=sqrt(N);”，將行12至行17的代碼改寫如下(其他部分不變，將改寫后的算法記為算法b)：

for(i=2;i<=k;i++)

if(a[i]!=0)

for (j=i+1;j<=N;j++)

{if (a[j]!=0 && (a[j]%a[i]==0))

a[j]=0;RepeatTimes++;}

for (i=2;i<=N;i++)

a[i]=1;

for(i=2;i<=k;i++)

if(a[i])

for(j=i<<1;j<=N;j+=i)

{ if(a[j])

a[j]=0;RepeatTimes++;}

2.3 算法的時間復(fù)雜度分析

3 測試結(jié)果及分析

測試機(jī)器配置為6 GB內(nèi)存，處理器為Intel Celeron 2.50 GHz，操作系統(tǒng)為64位Windows 8.1企業(yè)版.我們指定n=250 000，3個算法分別運(yùn)行10次，取平均運(yùn)行時間作為算法的運(yùn)行時間.測試結(jié)果如表1所示.

表1 算法測試結(jié)果

測試結(jié)果與對算法的分析基本吻合.由此可見，較好的算法優(yōu)化策略能顯著提高程序的執(zhí)行效率.

[1] 譚浩強(qiáng). C程序設(shè)計(jì)[M]. 4版.北京:清華大學(xué)出版社,2010:21.

[2] 何德彪,陳建華,胡志金. 雅克比和素性判別方法的軟件實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2007,28(16):3818-3821.

[3] 張琦,許勇. Matlab環(huán)境下素數(shù)篩選算法的分析及比較[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(3):95-98.

[4] GRAHAM R L,KNUTH D E,PATASHNIK O．具體數(shù)學(xué):計(jì)算機(jī)科學(xué)基礎(chǔ)[M].張明堯,張凡，譯. 2版. 北京:人民郵電出版社,2013:376.

[5] CORMEN T H,LEISERSON C E,RIVEST R L, et al．算法導(dǎo)論[M].殷建平,徐云，王剛,等,譯. 3版. 北京:機(jī)械工業(yè)出版社,2013:565.

Implementation and Optimization of Prime Sieve Method

ZHANG Guoqin, SONG Wei, MA Junxing

(CenterofModernEducationalTechnology,HenanInstituteofFinanceandBanking(LongzihuCampus),Zhengzhou450046,China)

An algorithm is designed according to the idea of prime sieve method, and it is optimized. The time complexity of the algorithm is analyzed, and the algorithm is measured by two indexes: the average running time and the main code execution times. The test results show that the optimized algorithm has high execution efficiency.

prime number; sieve method; optimization; time complexity; execution efficiency

2017-01-19

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目計(jì)劃(16A520008)

張國欽(1975—)，男，河南南陽人，河南財政金融學(xué)院(龍子湖校區(qū))現(xiàn)代教育技術(shù)中心工程師.

10.3969/j.issn.1007-0834.2017.01.008

TP311.1

A

1007-0834(2017)01-0039-03