姚凯哲 吕雅文 许天启 童尧

摘要：本文对传统的素数筛选算法的缺点进行了分析和改进。并在埃拉托斯特尼筛法（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]中的所有素数。埃氏筛法原理简单，实现起来比较容易。