素数筛选算法的一种改进

姚凯哲 吕雅文 许天启 童尧

摘要：本文对传统的素数筛选算法的缺点进行了分析和改进。并在埃拉托斯特尼筛法（sieve of Eratosthenes）的基础之上，设计了一种基于已知素数来寻找未知素数的区间筛法。区间筛法突破了由计算机内存分配造成的数量级限制，大幅提升了寻找素数的范围，并通过优化筛选过程提升了算法运行速度。实验结果表明，经过改进的区间筛法在筛选范围上远大于传统筛法，并且具有较好的时间复杂度。

关键词：素数；筛法；区间筛法；筛选范围

中图分类号：TP301 文献标識码：A 文章编号：1009-3044（2018）17-0075-02

1 引言

素数，是数论中最古老、最基本但至今仍受到广泛关注的话题之一。围绕着素数产生了一系列世界级的难题，吸引了历史上一大批著名的数学家参与其中，其中有很多问题至今仍未解决。筛法是寻找素数的一种常见而又高效的方法。寻找与判别素数的算法在现代信息科学与程序设计中起着相当重要的作用。

2 经典的素数筛选法

2.1 埃拉托斯特尼筛法

埃拉托斯特尼筛法（sieve of Eratosthenes）简称埃氏筛或爱氏筛， 是一种由埃及数学家埃拉托斯特尼所提出的一种简单检定素数的算法。他的方法是：先将2～[n]从小到大排列。选中2，然后将2的其他倍数筛去；再选中下一个未被筛去的数3，将3的其他倍数都筛去；下一个未被筛除的数是5，将5的其他倍数筛去……以此类推，一直到没有数可以被选择为止，剩下未被筛除的数即为2～[n]中的所有素数。埃氏筛法原理简单，实现起来比较容易。它的算法复杂度为[O（nloglogn）]。

2.2 线性筛法——欧拉筛法

埃氏筛法虽然原理简单，速度较快，但是筛选过程中任意一个合数都会被它的[k]个素因子处[k]理次，造成大量不必要的计算。因此，欧拉筛法就是对这点不足的改进。对于从2开始的每个自然数[i]，先将每个发现的素数归入集合[P]中，然后将集合[P]中的每一个素数的[i]倍筛去。当[i]被[P]中某个素数整除时，便立即进入下一轮筛选，直到所有[n]以内的数都被处理过为止。这时，[P]中就包含了[n]以内的所有素数。这种算法保证了每一个合数都只被自己的最小素因子处理一次，大幅减少了多余的运算，提高了运算效率。欧拉筛法的时间复杂度为[O（n）]，因此又被称为线性筛法。

2.3 传统筛法的不足之处

在传统筛法算法中，获取[n]以内的素数需要消耗与[n]等量大小的内存。这导致[n]过大时，计算机无法提供足够的内存，导致程序崩溃。传统筛法的另一个缺点是只能一次性获取2～[n]之间的素数，而不能仅仅获取任一个区间内素数。若只要求某一区间内的素数则会造成程序在运行时大量不必要的内存消耗，并且极大地限制了区间的可行范围。

3 筛法的改进

对于传统筛法的上述缺点，本文提出了分区间筛选的思想并对算法的以下几处进行改进优化，使得通过筛法可以获得更大范围内的素数，并且不受起始数的限制。

3.1 使用已知素数进行筛选

定理1 若[n≥2]是合数，则必有质数[p|n]，[p≤n].

通过算数基本定理可知，每个合数都可以分解成若干个素数的乘积，因此只要验证一个数是否被某个素数整除就可以判断它是否为合数，这是就筛法的基本思想。根据定理1，该数的最小的素因子不会超过它的平方根。因此，若现在已知前2～[n]范围内素数，则通过遍历一次整个素数集合可以快速计算出[n2]以内全部的素数。

3.2 分区间筛选

传统筛法寻找素数时，由于没有任何已知素数，因此需要从第一个素数2开始计算，筛选序列的构造也必须从2开始，很大程度上限制了筛选的范围。由之前的讨论可知，若已知2～[n]范围内素数，则可以对筛法算法进行适当的改进，从而获得[n2]以内任一区间里的素数。这种方法有效的摆脱了传统筛法对筛选起点的限制。

图1展示了区间筛法的计算过程。其中[n]以内的素数集可以通过传统筛法程序事先得到。由于线性筛法的算法原理在分区间的筛法上并不适用，因此这里使用了埃氏筛法的算法原理进行筛选。对于区间[[m，n]]，需使用[n]内的素数进行筛选，所以该算法的时间复杂度为[O（（n-m）loglogn）]，比埃氏筛法的复杂度稍低一些。

3.3 区间筛法的优化

对于区间筛法，在实际的编程中还可以对以下几部分进行优化，以加快速度并减少空间占用率。

3.3.1 去偶存奇

除2以外的偶数都不是素数，因此在筛选时可以直接略去偶数，只考虑奇数。对筛选数组的相应下标做映射[S]：[n→2n+1]，在判定时通过做逆映射修改相应下标的值来完成筛选，这样做使筛选数组的大小比原来缩小了一倍。去偶操作不仅降低了程序的内存占用率，同时省去对偶数的筛除也提高了算法的效率。

3.3.2 优化筛选因数范围

在计算过程中，调整筛选因数的取值范围可以去除冗余的运算。筛法算法的具体实现里通过将素数[p]与另一数[i∈Ip]相乘来筛除素因子为[p]的合数，这里[Ip]表示所有与[p]相乘的因数的集合。由于是在某一区间中筛选素数，所以当[p]改变时，集合[Ip]中的元素也会相应的改变，[i]的取值范围随着[p]的增大而减小。事实上，若要筛去区间[[m，n]]中素因子为[p]的偶数，则因子[i]只需取[[m/p]+1]到[[n/p]+1]之间的所有奇数即可。

定理2 当[Ip]中最存在小于[p]的因数时，可以将[Ip]中小于[p]的元素去除。

证明：[?i∈][Ip]满足[i

根据定理2，在设计算法时对[Ip]的范围做适当的调整，可以防止一部分数被重复筛选。

综合上述两处对算法优化，用C++实现的核心代码如下：（对区间[[M，N]]筛选）

3.4 扩大筛选范围

运用区间筛法，通过对较大的区间进行合理的划分并迭代计算可以大幅扩大筛选的范围。并且可以将每一次新的筛选结果存入素数集中，扩大的素数集将为更大数量级的筛选提供保证。

图2展示了在大区间内筛选素数的基本过程。例如需要计算1000亿以内的素数。假设程序一次最多只能在10亿大小的区间筛选，则可以将1000亿的区间以10亿大小等分为100个子区间。首先用线性筛法获得2～10亿内的素数集并保存，然后用区间筛法对之后的每个子区间进行计算，每轮计算完成后将结果添加到已有的素数集中，为以后的筛选提供素数。经过反复迭代即可获得1000亿以内的素数集。

事实上，只要预先输入一小部分从3开始的素数，该算法就能通过合理的分配筛选区间迭代计算出任意规模大小内的所有素数，打破了传统筛法对空间上的限制。

4 实验结果分析

本文使用C++實现了三种算法，并且分别选取了1亿，5亿，10亿的区间来测试它们寻找素数所需的内循环次数，具体结果如图3所示：

可以看到，经过优化的区间筛法循环次数已经十分接近线性的欧拉筛法，与原始的埃氏筛法相比有很大的改进。

同时还给出了三种算法在实际程序运行中最大的可筛选素数范围，结果见表1：

5 结语

传统的埃氏筛法与欧拉筛法可以在短时间里快速地寻找出素数，但在范围上受到了限制。区间筛法通过使用已经得到的素数集在某个区间内寻找新的素数，同时在奇偶判定、缩小筛选因数范围两方面对算法进行优化，突破了传统的筛法在范围上的局限。通过将传统筛法与区间筛法相结合并合理划分区间，可以大幅提升筛选素数的范围。

参考文献：

[1] 闵嗣鹤，严士键.初等数论[M].第三版.高等教育版社，2003，12：14-18.

[2] 司钊，司琳.哥德巴赫猜想与优化筛法[M].西北工业大学出版社，2005，9：10-14.

[3] 叶煜，周洪林，任华.素数筛选法的改进及C语言实现[J].计算机与数字工程，2013，6：899-900.

[4] 高晓巍，郑大钊.查找素数的有效方法及在计算机上的实现[J].高师理科学刊，2005，8：9-12.