基于Eratosthenes算法快速求解質數的程序設計

孫東雪

西南民族大學計算機科學與技術學院，四川成都 610041

0 引言

質數在數論這個學科中占有十分重要的地位。在密碼學、生物學以及工程問題上都有廣泛的應用。自(2013 年1 月25 日）美國中央密蘇里大學發(fā)現了目前最大的素數以來，數論這一純粹數學分支在數學界又一次引起了強烈轟動。

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

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

1 基礎概念

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

2 算法介紹及程序實現

2.1 Eratosthenes 算法

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

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

1）刪掉1，第一個留下的是2，它是第一個質數，如下所示：

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

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

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

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

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

如此進行下去，留下的都是質數，這就是Eratosthenes算法

2.2 程序實現

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

程序分析：該程序采用matlab 向量運算，當檢測到此數為合數時，其值被重置為，為每個過程中的首個質數。向量的作用僅僅是為了找到每個過程中的首個質數，進而補充到向量中。向量為真正的質數向量。

2）采用普通算法求質數的程序如下：

3）采用自帶求質數的函數程[5]序如下：

對輸入的正整數，分別用三個程序進行求解，結果一致，求得的質數結果如表1 所示。

表1 三個程序求解質數的結果

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

表2 三個程序執(zhí)行時間的對比

3 結論

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

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

[2]閔嗣鶴，嚴士健.初等數論[M].高等教育出版社，2003.

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

[4]紀崗.Matlab 語言在初等數論中的應用[J].福建師大福清分校學報，2013，2：007.

[5]MATLAB 應用數學工具箱技術手冊[M].國防工業(yè)出版社，2004.