素数判断算法综述与程序实现

吕橙，李敏杰

（北京建筑大学计算机系，北京100044）

0 引言

素数的研究一直是数论研究的热点之一，也是计算机等级考试或各类编程竞赛常考的知识点之一，尤其是大数判断也是密码学的基础。素数的定义：如果一个整数n 只有1 和n 两个因子，则p 为素数，亦称为质数。合数的定义：不为素数的其他数为合数。如果n为合数，则n 必有一个小于或等于n 的平方根的数因子。素数的判定方法是对输入的整数判定是素数还是合数，本文对已有的方法进行梳理，并给出算法模板。

1 算法分析与实现

1.1 朴素判别法

定理1n＞1 是素数，当且仅当不大于√n的所有素数都不能整除n。

这种算法是最直接，最简单的素数判断法，又称为朴素判别法、或试除法，即判断n 是否为素数，根据素数定义，可以用n 除以从2～n-1 之间所有的数，如果能整除，则说明不是素数，否则就是素数。事实上，试除的范围可以不用2～n-1，而用2～√n即可。试除法的计算量是O（√nlog22n。

C 语言模板如下：

说明：返回0 代表是合数，返回1 代表是素数。

1.2 埃拉托斯特尼（Eratosthenes）筛选法

埃拉托斯特尼筛选法，这个古老的筛选法在构造素数表时，仍然起着很大的作用，给定一个n，要找出不大于n 的所有素数，可以将1，2，…，n 按自然顺序排列好。第一步：删去第一个未被删去或圈住的数；第二步：将第一个未被圈住和删去的数圈住，删去所有这个刚被圈住的数的倍数。在执行第一次第一步时，是删除1，第一次执行第二步时，圈住2 并删除2 的倍数，然后回转重复第二步、…、这样若干次执行第二步直到不大于√n的每个数都被删除或圈住为止，这时，被圈住的和剩下来未被删去和圈住的数便是不大于n 的全部素数。

例1 判别7393 是否是素数1。

解：√7393=85，先用埃拉托斯特尼筛选法找出不大于85 的所有素数：将1 至85 的数按自然顺序排列好，然后，循环地执行上述第二步直至不大于√85≈9的数全被删去或圈住为止。即得85 之下的素数是2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83。

1 k l 4 n 6 p 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

由上表可以看出，圈住和未被删去的即为素数。

C 代码如下：

1.3 高效判别法

现在让我们讨论一下素数出现的规律。当n＞=5时，如果 n 为素数，那么 n mod 6=1 或 n mod 6=5，即n 一定出现在 6x（x≥1）两侧2。

稍微证明一下：

当x≥1 时，有如下表示方法：

……，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6（x+1），6（x+1）+1，……

不在 6x 两侧的数为 6x+2，6x+3，6x+4，即 2（3x+1），3（2x+1），2（3x+2），它们一定不是素数，所以素数 n一定出现在6x 的两侧。

故此，我们只需判断6 的倍数两侧的数即可。

C 代码如下：

1.4 费马小定理

试除法出现之后，一直到16 世纪，期间除了一些特殊的、很局限的素数判别法外，没有什么重要的结果，但到了1640 年，法国数学家费马注意到了素数的一个性质，这就是费马小定理。

定理2费马小定理。若n 是素数数，则对所有不被 n 整除的 a，有 an-1≡ 1（mod n）。

定义、对整数 a＞1，满足 an≡ a（mod n）的合数 n 称为底为n 的伪素数。

定理3对每一个整数a＞1，有无限多个底为a 的伪素数。

这样的伪素数（合数）的存在是费马小定理的逆命题不成立的最合适的例证，是由卡米歇尔首先发现的，故叫卡米歇尔数。费马测试是判断一个数是否为素数的一个基于概率的测试，即不保证所找出的素数的正确性，但错误可能性却小到可以接受。

费马测试的具体实现是，对于n，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，n 仍未测试失败，那么则认为n 是素数。当然，测试的次数越多越准确，但一般来讲50 次就足够了。另外，预先构造一个包括500 个素数的数组，先对n 进行整除测试，将会大大提高通过率。

C 代码如下：

1.5 欧拉函数与欧拉筛选

埃拉托斯特尼已经很高效了，但是很明显，埃拉托斯尼算法还是有一定的缺陷的，例如埃拉托斯尼算法中，有的合数被重复筛除，例如30，2*15 筛了一次，5*6重复筛除。由于任何合数都能表示成一系列素数的积。然后利用了每个合数必有一个最小素因子，每个合数仅被它的最小素因子筛去正好一次。

C 代码如下：

1.6 米勒拉宾测试（Miller-Rabin）

在小费马定理的基础上有人设计出米勒拉宾随机素数测试法，大大的提高检测素数的正确性。令n-1=2fm，其中 f 是非负整数，m 是正奇数。若 bm≡ 1（mod n）或 b2fm≡ -1（mod n），则 0≤j≤f-1 称一通过以 b 为基的 Miller-Rabin 测试3。

C 代码如下：

2 结语

本文对几种素数判断方法进行了综述，并给出了C 语言的算法模板，各种算法可以解决实际工作中的一些相关问题，具有一定的实际意义。用C 语言实现的算法模板有助于读者更好地理解和把握该算法的基本思想和实现过程。