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

張國欽， 宋 偉， 馬俊興

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

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

張國欽， 宋 偉， 馬俊興

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

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

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

0 引言

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

1 素?cái)?shù)的判斷方法

1.1 基本試除法

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

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

2 篩選法求素?cái)?shù)的算法及優(yōu)化

2.1 篩選法求素?cái)?shù)的算法思想

素?cái)?shù)篩選法的基本思想是把一定范圍內(nèi)的自然數(shù)中不是素?cái)?shù)的數(shù)劃去，剩下的就是素?cái)?shù).依據(jù)是自然數(shù)中除了1之外，不是素?cái)?shù)，就是合數(shù).篩選法求素?cái)?shù)的過程描述如下：把不超過N的所有自然數(shù)按從小到大的順序排列起來；1既不是素?cái)?shù)，也不是合數(shù)，劃去；2是素?cái)?shù)，把2留下，再把2后面所有能被2整除的數(shù)都劃去；2后面第一個(gè)沒劃去的數(shù)是3，把3留下，再把3后面所有能被3整除的數(shù)都劃去；3后面第一個(gè)沒劃去的數(shù)是5，把5留下，再把5后面所有能被5整除的數(shù)都劃去；這樣一直做下去，就會(huì)把不超過N的全部合數(shù)都篩掉，留下的就是不超過N的全部素?cái)?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(" 求素?cái)?shù)所用時(shí)間:time=%.3lf秒 ",(double)(end-start)/CLOCKS_PER_SEC);

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

21 //輸出素?cái)?shù)的代碼，不是算法的主要部分，略去；

28 return 0; }

在算法a中加入了執(zhí)行時(shí)間和循環(huán)次數(shù)等直觀表示算法執(zhí)行效率的度量指標(biāo).該算法可以進(jìn)一步優(yōu)化.行12的語句中函數(shù)調(diào)用sqrt(N)作為條件表達(dá)式的一部分，每次判斷都要用到，因此可以把該值放在for語句之前計(jì)算出來以備調(diào)用(雖然編譯器可以對(duì)此進(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 算法的時(shí)間復(fù)雜度分析

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

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

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

測(cè)試結(jié)果與對(duì)算法的分析基本吻合.由此可見，較好的算法優(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)境下素?cái)?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—)，男，河南南陽人，河南財(cái)政金融學(xué)院(龍子湖校區(qū))現(xiàn)代教育技術(shù)中心工程師.

10.3969/j.issn.1007-0834.2017.01.008

TP311.1

A

1007-0834(2017)01-0039-03