埃拉托色尼筛法（，），或作埃拉托斯特尼筛法，簡稱-{zh-cn:埃氏筛; zh-tw:埃氏篩; zh-hk:愛氏篩}-，是一种用來質數的筛法，得名於古希臘數學家埃拉托色尼。其基本步骤是從最小的質數2開始，將该質數的所有倍數標記成合數，而下一个尚未被标记的最小自然数3即是下一个質數。如此重复这一过程，将各个质数的倍数标记为合数并找出下一个质数，最终便可找出一定範圍內所有質數。
埃拉托色尼筛法可能在埃拉托色尼的时代之前就已经为人所知，并记载于另一位古希腊数学家尼科马库斯的《》中，尽管该著作中的这一筛法是从3开始，从奇数中依次筛去奇数的倍数，而非从自然数中筛去质数的倍数。
运用与示例
埃拉托色尼筛法通过不断地标记当前质数的所有倍数为合数，从而取得最小的未标记整数为下一个質數。不过，在实际使用此筛法寻找一个范围内的質數时，不需要检查范围内所有整数，也不需要对每个質數都标记其所有的倍数。
#寻找N以内的質數时，若找到了一个大于\sqrt{N}的质数，则剩余的所有尚未标记的数也都是質數。
#:证明：若这些尚未标记的数中有任意一个为合数，设之为m，则m必定是除1与自身以外的两个因数的乘积。但既然m尚未被标记，则所有小于等于\sqrt{N}的数均不是m的因数。故这两个因数必然都大于\sqrt{N}，则m不可能在N以内。
#标记某一質數p的倍数时，不需要每次皆从2 p, 3 p, \ldots开始，而可直接从p^2开始标记。
#:证明：所有较p^2更小的p的倍数必然拥有一个更小的质数为其因数，故在标记之前的质数的倍数时它们已经被标记过了。
若要找出25以内的所有质数，使用如上述改进过的埃拉托色尼筛法的具体过程如下：
#列出2以後所有數：
#:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
#记录質数2，由2=4开始划去2的倍数：
#:2 3 5 7 9 11 13 15 17 19 21 23 25
#记录下一質数3，由3=9开始划去3的倍数：
#:2 3 5 7 11 13 17 19 23 25
#记录下一質数5，由5=25开始划去5的倍数：
#:2 3 5 7 11 13 17 19 23
#下一質数为7，而7=49>25，故剩余所有未标记的数皆为質数：
#:2 3 5 7 11 13 17 19 23
由此得到25內的質数为2，3，5，7，11，13，17，19，23。
以上的算法可用以下虛擬碼;}-表示：
-{zh-cn:
输入：整数n > 1
设A为布尔值矩阵，下标是2至n的整数，
初始时全部设成true。
for i = 2, 3, 4, ..., 不超过：
if A[i]为true：
for j = i2, i2+i, i2+2i, i2+3i, ..., 不超过n：
A[j] := false
输出：使A[i]为true的所有i。;zh-tw:
輸入：整數n > 1
設A為布爾值陣列，指標是2至n的整數，
初始時全部設成true。
for i = 2, 3, 4, ..., 不超過：
if A[i]為true：
for j = i2, i2+i, i2+2i, i2+3i, ..., 不超過n：
A[j] := false
輸出：使A[i]為true的所有i。;}-
埃拉托色尼筛法的时间复杂度为O(n\log (\log n))；相比之下，若是通过对范围内每个整数进行试除法来找出范围内的质数，则其时间复杂度为O(n\sqrt {n})。
代码
Python 3.6-3.10
def eratosthenes(n):
is_prime = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [x for x in range(2, n + 1) if is_prime[x]]
print(eratosthenes(120))
C語言
int prime[100005];
bool is_prime[1000005];
int eratosthenes(int n) {
int p = 0;
for (int i = 0; i
C語言新版
#include
#include
/* N: positive integer
verbose: 1 -- print all prime numbers
C++
#include
auto eratosthenes(int upperbound) {
std::vector flag(upperbound + 1, true);
flag[0] = flag[1] = false; //exclude 0 and 1
for (int i = 2; i * i
R
eratosthenes
JavaScript
const countPrimes = function (n) {
const isPrime = new Array(n).fill(true);
for (let i = 2; i
参见
*篩法
*卢卡斯-莱默检验法
*米勒-拉宾检验
*试除法
*费马素性检验
*孪生素数
*三胞胎素数
*四胞胎素数
*素数判定法则
*表兄弟素数
*六素数
*X²+1素数
*勒讓德篩法
*
*
*
参考文献
拓展阅读
*[http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm Interactive animation (需要JavaScript)]
*[https://coolshell.cn/articles/3738.html 打印质数的各种算法]
*[https://web.archive.org/web/20180220153640/http://debug18.com/posts/introduction-to-sieve-method/ 筛法小结 (Eratosthenes/Euler)]
*[http://blog.csdn.net/lytning/article/details/24432651 欧拉函数线性筛法详解] （欧拉函数线性筛）
*[http://blog.csdn.net/dinosoft/article/details/5829550 一般筛法求素数+快速线性筛法求素数(较好理解)]
评论 (0)