基于Eratosthenes算法快速求解質(zhì)數(shù)的程序設(shè)計(jì)

孫東雪

西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川成都 610041

0 引言

質(zhì)數(shù)在數(shù)論這個(gè)學(xué)科中占有十分重要的地位。在密碼學(xué)、生物學(xué)以及工程問題上都有廣泛的應(yīng)用。自(2013 年1 月25 日）美國(guó)中央密蘇里大學(xué)發(fā)現(xiàn)了目前最大的素?cái)?shù)以來，數(shù)論這一純粹數(shù)學(xué)分支在數(shù)學(xué)界又一次引起了強(qiáng)烈轟動(dòng)。

在科學(xué)研究與具體問題中，常常需要判定一個(gè)數(shù)是否為質(zhì)數(shù)或者需要求出某個(gè)正整數(shù)范圍內(nèi)質(zhì)數(shù)的個(gè)數(shù)，且分別為多少。針對(duì)這些問題，相關(guān)學(xué)者也已經(jīng)進(jìn)行過探討，例如：在紀(jì)崗（2013）“Matlab 語言在初等數(shù)論中的應(yīng)用”一文中，采用的往往是利用循環(huán)結(jié)構(gòu)求質(zhì)素，沒有用到系統(tǒng)、有效的算法，因而程序在范圍數(shù)較大的情況下效率較低。另有學(xué)者在探討此問題時(shí)，并沒有把程序所用時(shí)間考慮進(jìn)去，因而很難判別不同算法孰優(yōu)孰劣。

本文對(duì)目前求質(zhì)數(shù)的方法做了補(bǔ)充與改進(jìn)。首先簡(jiǎn)單介紹質(zhì)數(shù)的概念，然后依據(jù)Eratosthenes 算法設(shè)計(jì)程序。利用此程序，分別與matlab 自帶的判定質(zhì)數(shù)的函數(shù)、普通算法求解某個(gè)正整數(shù)范圍內(nèi)的質(zhì)數(shù)，對(duì)比各個(gè)程序執(zhí)行所用的時(shí)間，得到一個(gè)較優(yōu)的方案。

1 基礎(chǔ)概念

根據(jù)初等數(shù)論一書，質(zhì)數(shù)有嚴(yán)格的定義。一個(gè)大于1 的整數(shù)，如果它的正因數(shù)只有1 及本身，就叫做質(zhì)數(shù)；否則就叫做合數(shù)。除了2 既是質(zhì)數(shù)又是偶數(shù)外，其他質(zhì)數(shù)均是奇數(shù)。要判定一個(gè)正整數(shù)是否為質(zhì)數(shù)，普通算法是用2 到這個(gè)正整數(shù)減一的整數(shù)去除這個(gè)正整數(shù)，如果在這個(gè)過程中沒有出現(xiàn)整除的情況，則這個(gè)正整數(shù)是質(zhì)數(shù)。例如：對(duì)于正整數(shù)7，分別用2，3，4，5，6 去除7，都不能整除，則判定7 為質(zhì)數(shù)。

2 算法介紹及程序?qū)崿F(xiàn)

2.1 Eratosthenes 算法

給定一個(gè)正整數(shù)N，把不超過N 的所有正整數(shù)按從小到大順序排成一列

1,2,3,4,5,6,7,8,9,10,…,N

1）刪掉1，第一個(gè)留下的是2，它是第一個(gè)質(zhì)數(shù)，如下所示：

1,2,3,4,5,6,7,8,9,10,…,N

2）從2 起每隔一位刪掉一個(gè)數(shù)，這樣刪掉的數(shù)為2+2m（2本身除外），如下所示：

1,2,3,4,5,6,7,8,9,10,…,N

3）從3 起每隔兩位刪掉一個(gè)數(shù)，這樣刪掉的數(shù)為3+3m（3本身除外），如下所示：

1,2,3,4,5,6,7,8,9,10,…,N

如此進(jìn)行下去，留下的都是質(zhì)數(shù)，這就是Eratosthenes算法

2.2 程序?qū)崿F(xiàn)

1）按照此算法編寫的matlab 程序如下：

程序分析：該程序采用matlab 向量運(yùn)算，當(dāng)檢測(cè)到此數(shù)為合數(shù)時(shí)，其值被重置為，為每個(gè)過程中的首個(gè)質(zhì)數(shù)。向量的作用僅僅是為了找到每個(gè)過程中的首個(gè)質(zhì)數(shù)，進(jìn)而補(bǔ)充到向量中。向量為真正的質(zhì)數(shù)向量。

2）采用普通算法求質(zhì)數(shù)的程序如下：

3）采用自帶求質(zhì)數(shù)的函數(shù)程[5]序如下：

對(duì)輸入的正整數(shù)，分別用三個(gè)程序進(jìn)行求解，結(jié)果一致，求得的質(zhì)數(shù)結(jié)果如表1 所示。

表1 三個(gè)程序求解質(zhì)數(shù)的結(jié)果

進(jìn)而利用三個(gè)程序分別求解5000，10000，…，40000 以內(nèi)的質(zhì)數(shù)，并比較程序執(zhí)行所用的時(shí)間，如表2 所示。

表2 三個(gè)程序執(zhí)行時(shí)間的對(duì)比

3 結(jié)論

使用基于Eratosthenes 算法、普通算法、matlab 自帶的isprime 函數(shù)所設(shè)計(jì)的程序，分別來求解5000，10000，…，40000 以內(nèi)的質(zhì)數(shù)，三個(gè)程序所求結(jié)果一致，質(zhì)數(shù)個(gè)數(shù)均依次為669，1229，1754，2262，2762，3242，3732，4203.但 是程序執(zhí)行所用的時(shí)間大不相同，從整體上看，Eratosthenes算法最優(yōu)，普通算法次之，自帶函數(shù)最差，隨著范圍數(shù)的增大，差距還將進(jìn)一步拉大。從本文可以看出，基于Eratosthenes算法設(shè)計(jì)出來的求解質(zhì)數(shù)的程序，不僅從準(zhǔn)確度還是效率方面，都是優(yōu)良的。

[1]徐小華.素?cái)?shù)的快速程序求法[J].福建電腦，2008，24(11)：189.

[2]閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].高等教育出版社，2003.

[3]黃欣陽，伍紅茹.改良的 Eratosthenes 篩法[J].湖南環(huán)境生物職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2004，10(3)：253-256.

[4]紀(jì)崗.Matlab 語言在初等數(shù)論中的應(yīng)用[J].福建師大福清分校學(xué)報(bào)，2013，2：007.

[5]MATLAB 應(yīng)用數(shù)學(xué)工具箱技術(shù)手冊(cè)[M].國(guó)防工業(yè)出版社，2004.