瞭解Python中Eratosthenes的篩選器

Question

我在python中找到了一個示例代碼，它給出了所有素數高達n，但我根本不明白，爲什麼它會執行它的功能？

我已閱讀維基百科有關Sieve of Eratosthenes的文章，但完全不知道這是如何工作的。

pp = 2 
ps = [pp] 
lim = raw_input("Generate prime numbers up to what number? : ") 
while pp < int(lim): 
    pp += 1 
    for a in ps: 
     if pp%a==0: 
      break 
     else: 
      ps.append(pp) 


print set(ps) 

有關如何循環工作的解釋將不勝感激。

編輯 -想通了，該代碼是完全錯誤的它表示25作爲主要通過發現，這不是沒有篩網更深入的搜索，可有人告訴它利用篩在python的發電機和解釋它

Answer 1

該代碼是嘗試使用試劃分生成一系列素數。

要更正：

pp = 2 
ps = [pp] 
lim = raw_input("Generate prime numbers up to what number? : ") 
while pp < int(lim): 
    pp += 1 
    for a in ps: 
     if pp%a==0: 
      break 
    else:    # unindent 
     ps.append(pp) # this 

爲了使它更有效（其實，最佳）審判庭：

pp = 2 
ps = [pp] 
lim = raw_input("Generate prime numbers up to what number? : ") 
while pp < int(lim): 
    pp += 1 
    for a in ps: 
     if a*a > pp:   # stop 
      ps.append(pp) # early 
      break 
     if pp%a==0: 
      break 

Answer 2

首先，這不是一個篩子。

這是如何工作的。 pp是我們要測試的數字。在while循環的每次迭代中，我們遍歷所有已知的素數（ps）並檢查它們是否將pp分開。如果其中之一，pp不是主要的，我們移動到下一個數字。否則，在繼續之前，我們將pp添加到素數列表中。

線pp%a==0基本上是說「上，當a除以pp的remander是零」，即a分pp和pp不是素數。

這繼續直到我們正在檢查的數量比，我們已經設置一些上限大（lim）

[編輯：這是一個篩]

isPrime = [True for i in range(lim)] 
isPrime[0] = False 
isPrime[1] = False 

for i in range(lim): 
    if isPrime[i]: 
     for n in range(2*i, lim, i): 
      isPrime[n] = False 

這不是最有效的篩選（更有效率的在for n in range(2*i, lim, i):行中執行操作，但它會起作用，並且isPrime[i]將是true if i是prime。

Answer 3

上述實現會產生錯誤的答案。我對代碼做了一些修改。

但是，以上代碼的工作原理如下。

pp = 2 
ps = [pp] 

我們知道，第一個素數是2，所以，我們生成僅包含數字2列表。

lim = raw_input("Generate prime numbers up to what number? : ") 

上面的這行代碼是從用戶那裏得到的一個輸入，它給出了要生成的素數的上限。

while pp < int(lim): # 1 
     pp += 1   # 2 
     primeFlag = True # 3 
     for a in ps:  # 4 
      if pp%a==0: 
      primeFlag = False 
      break 
     if primeFlag:  # 5 
      ps.append(pp) 

帶數字的行做下列事情。

1. 運行循環直到達到上限。
2. 將pp變量加1。
3. 設置一個標誌變量，用於測試數字是否爲素數。
4. 了存儲在ps和素數的列表此for循環迭代檢查，目前的數量，pp是這些數字中的任何一個整除，如果是，那麼這個數是不是素數和primeFlag設置爲False和我們打破了內部for循環。
5. 如果數量沒有任何之前的素數整除，那麼它必須是一個素數，因此，變量primeFlag是True和if聲明追加列表ps與pp。

Answer 4

既然沒有人還沒有顯示出真正的篩子或解釋， 我會嘗試。

基本方法是從2開始計數並消除2 * 2和2的所有更高倍數（即4,6,8 ...），因爲它們都不是素數。 3在第一輪存活，所以它是總理，現在我們消除3 * 3和3的所有更高的倍數（即9,12,15 ...）。 4個被淘汰，5個倖存下來等。每個素數的平方是一個優化，利用了每個新素數的所有較小倍數將在前幾輪被淘汰的事實。使用這個過程來計算和消除非素數時，只有素數會留下。

這是一個非常簡單的版本，發現它不使用模數師或根：

def primes(n): # Sieve of Eratosthenes 
    prime, sieve = [], set() 
    for q in xrange(2, n+1): 
     if q not in sieve: 
      prime.append(q) 
      sieve.update(range(q*q, n+1, q)) 
    return prime 

>>> primes(100) 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73 
79, 83, 89, 97] 

上面的簡單的方法是出奇的快，但不利用這一素數只能是奇數的事實。

這是一個基於生成器的版本，比我發現的任何其他版本都快，但在我的機器上n = 10 ** 8時達到Python內存限制。

def pgen(n): # Fastest Eratosthenes generator 
    yield 2 
    sieve = set() 
    for q in xrange(3, n+1, 2): 
     if q not in sieve: 
      yield q 
      sieve.update(range(q*q, n+1, q+q)) 

>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10) 
5.987867565927445 

這裏有一個稍微慢一些，但更多的內存高效發電機版本：

def pgen(maxnum): # Sieve of Eratosthenes generator 
    yield 2 
    np_f = {} 
    for q in xrange(3, maxnum+1, 2): 
     f = np_f.pop(q, None) 
     if f: 
      while f != np_f.setdefault(q+f, f): 
       q += f 
     else: 
      yield q 
      np = q*q 
      if np < maxnum: 
       np_f[np] = q+q 

>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10) 
7.420101730225724 

>>> list(pgen(10)) 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 

測試一個數是素數只是做：

>>> 539 in pgen(539) 
False 
>>> 541 in pgen(541) 
True 

下面是一些提示，以這種更高效的內存版本如何工作。它使用dict來存儲最小的信息，下一個非素數（作爲關鍵字）及其因子（作爲值）。由於在dict中找到每個非素數，因此將其刪除，並使用相同的因子值添加下一個非主鍵。