孙东雪

西南民族大学计算机科学与技术学院，四川成都 610041

0 引言

质数在数论这个学科中占有十分重要的地位。在密码学、生物学以及工程问题上都有广泛的应用。自(2013 年1 月25 日）美国中央密苏里大学发现了目前最大的素数以来，数论这一纯粹数学分支在数学界又一次引起了强烈轰动。

在科学研究与具体问题中，常常需要判定一个数是否为质数或者需要求出某个正整数范围内质数的个数，且分别为多少。针对这些问题，相关学者也已经进行过探讨，例如：在纪岗（2013）“Matlab 语言在初等数论中的应用”一文中，采用的往往是利用循环结构求质素，没有用到系统、有效的算法，因而程序在范围数较大的情况下效率较低。另有学者在探讨此问题时，并没有把程序所用时间考虑进去，因而很难判别不同算法孰优孰劣。

本文对目前求质数的方法做了补充与改进。首先简单介绍质数的概念，然后依据Eratosthenes 算法设计程序。利用此程序，分别与matlab 自带的判定质数的函数、普通算法求解某个正整数范围内的质数，对比各个程序执行所用的时间，得到一个较优的方案。

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 以内的质数，并比较程序执行所用的时间，如表2 所示。

表2 三个程序执行时间的对比

3 结论

使用基于Eratosthenes 算法、普通算法、matlab 自带的isprime 函数所设计的程序，分别来求解5000，10000，…，40000 以内的质数，三个程序所求结果一致，质数个数均依次为669，1229，1754，2262，2762，3242，3732，4203.但 是程序执行所用的时间大不相同，从整体上看，Eratosthenes算法最优，普通算法次之，自带函数最差，随着范围数的增大，差距还将进一步拉大。从本文可以看出，基于Eratosthenes算法设计出来的求解质数的程序，不仅从准确度还是效率方面，都是优良的。

[1]徐小华.素数的快速程序求法[J].福建电脑，2008，24(11)：189.

[2]闵嗣鹤，严士健.初等数论[M].高等教育出版社，2003.

[3]黄欣阳，伍红茹.改良的 Eratosthenes 筛法[J].湖南环境生物职业技术学院学报，2004，10(3)：253-256.

[4]纪岗.Matlab 语言在初等数论中的应用[J].福建师大福清分校学报，2013，2：007.

[5]MATLAB 应用数学工具箱技术手册[M].国防工业出版社，2004.