本页使用了标题或全文手工转换

埃拉托斯特尼筛法

维基百科,自由的百科全书
跳转至: 导航搜索

埃拉托斯特尼(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$

参考文献[编辑]

  • Κοσκινον Ερατοσθενους 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.

参见[编辑]

外部連結[编辑]