埃拉托斯特尼篩法

維基百科,自由的百科全書
跳轉到: 導覽搜尋
Sieve of Eratosthenes

埃拉托斯特尼篩法,簡稱埃氏篩,是一種公元前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.

參見[編輯]

外部連結[編輯]