埃拉托斯特尼筛法

埃拉托斯特尼筛法，簡稱埃氏篩或愛氏篩，是一種公元前250年由古希臘数学家埃拉托斯特尼所提出的一種簡單檢定素数的算法。

算式

给出要筛数值的范围n，找出$\sqrt{n}$以内的素数$p_{1},p_{2},\dots,p_{k}$。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一個質數，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一個質數5筛，把5留下，把5的倍数剔除掉；不斷重複下去......。

步驟

详细列出算法如下：

1. 列出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，序列变成：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. 将剩下序列中，劃摽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
4. 如果现在这个序列中最大数小于最後一個標出的素數的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。

---

1. 本例中，因为25大于2的平方，我们返回第二步：
2. 剩下的序列中第一个素数是3，将主序列中3的倍数划出（红色），主序列变成：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1. 我们得到的素数有：2，3
2. 25仍然大于3的平方，所以我们还要返回第二步：
3. 现在序列中第一个素数是5，同样将序列中5的倍数划出，主序列成了：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. 我们得到的素数有：2 3 5 。
5. 因为25等于5的平方，跳出循环.

结论：去掉红色的数字，2到25之间的素数是：2 3 5 7 11 13 17 19 23。

---

下列是伪代码演算法：

// arbitrary search limit
limit ← 1.000.000                   

// assume all numbers are prime at first                                    
                                                                            
is_prime(i) ← true, i ∈ [2, limit] 

for n in [2, √limit]:
    if is_prime(n):
        // eliminate multiples of each prime,
        // starting with its square
        is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}

for n in [2, limit]:
    if is_prime(n): print n

可再簡化為：

limit = 1000000
sieve$ = string of the character "P" with length limit

prime = 2
repeat while prime2 < limit
    set the character at the index of each multiple of prime (excluding index prime * 1) in sieve$ to "N"
    prime = index of the next instance of "P" in sieve$ after index prime
end repeat

print the index of each instance of "P" in sieve$

黎曼猜想的素数公式与埃拉托斯特尼筛法关系

$\zeta (s) = \sum^{\infin}_{n=1} { 1 \over {n^s}}$

$\zeta(s) = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \cdots$ 。（5）

在等号两边乘以$\frac{1}{2^s}$，由幂运算规则得到。

$\frac{1}{2^s} \zeta(s) = \frac{1}{2^s} + \frac{1}{4^s} + \frac{1}{6^s} + \frac{1}{8^s} + \cdots$。（6）

我们从第（5）式子减去第（6）式子，在左边我有一个$\zeta(s)$. 又有它的$\frac{1}{2^s}$,做减法得：

（$1-\frac{1}{2^s}$）$\zeta(s) =1+ \frac{1}{3^s} + \frac{1}{5^s} + \frac{1}{7^s} + \frac{1}{9^s} + \frac{1}{11^s} + \frac{1}{13^s} + \frac{1}{15^s}+\cdots$。（7）

这个减法从那个无穷和中去掉了所有偶数项。现在在等号两边乘以$\frac{1}{3^s}$,而3是右边第一个还没有去掉的数：

$\frac{1}{3^s}$（$1-\frac{1}{2^s}$）$\zeta(s) = \frac{1}{3^s} + \frac{1}{9^s} + \frac{1}{15^s} + \frac{1}{21^s} + \frac{1}{27^s} + \frac{1}{33^s} + \frac{1}{39^s} +\cdots$。（8）

我们再做减法，第（7）式子减去这个式子，得： （$1-\frac{1}{3^s}$）（$1-\frac{1}{2^s}$）$\zeta(s) =1+ \frac{1}{5^s} + \frac{1}{7^s} + \frac{1}{11^s} + \frac{1}{13^s} + \frac{1}{17^s} + \frac{1}{19^s} + \frac{1}{23^s}+\cdots$。（9）

3的所有倍数都从那个无穷和中消失了，右边还有第一个没有被去掉的数是5，如果我们两边都乘以$\frac{1}{5^s}$,结果是：

$\frac{1}{5^s}$（$1-\frac{1}{3^s}$）（$1-\frac{1}{2^s}$）$\zeta(s) = \frac{1}{5^s} + \frac{1}{25^s} + \frac{1}{35^s} + \frac{1}{55^s} + \frac{1}{65^s} + \frac{1}{85^s} + \frac{1}{95^s}+\cdots$。（10）

从第（9）式子减去这个式子得：

（$1-\frac{1}{5^s}$）（$1-\frac{1}{3^s}$）（$1-\frac{1}{2^s}$）$\zeta(s) = 1+\frac{1}{7^s} + \frac{1}{11^s} + \frac{1}{13^s} + \frac{1}{17^s} + \frac{1}{19^s} + \frac{1}{23^s} + \frac{1}{29^s}+\cdots$。（11）

继续下去，对于大于1的任意s，左边对每一个带括号的表达式，并向右边一直继续下去，对这个式子的两边都依次逐个除以这些括号，我们得到：

$\zeta(s) = \prod_{p} \frac{1}{1-p^{-s}}$ =$\frac{1}{1-2^{-s}}\cdot\frac{1}{1-3^{-s}}\cdot\frac{1}{1-5^{-s}}\cdot\frac{1}{1-7^{-s}}\cdot\frac{1}{1-11^{-s}} \cdots \frac{1}{1-p^{-s}} \cdots.$。（12）

即： （5）式=（12）式

这就是重复埃拉托塞尼筛法的过程。也就是说，黎曼猜想不是凭空出现的，而是有埃拉托斯特尼筛法作为基础的。

参考文献

• Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

参见

• 卢卡斯-莱默检验法
• 米勒-拉宾检验
• 试除法
• 费马素性检验
• 孪生素数
• 三胞胎素数
• 四胞胎素数
• 素数判定法则
• 表兄弟素数
• 六素数
• X²+1素数

外部連結

• Interactive animation (需要JavaScript)