總理篩/範圍內的對

Question

我想寫一個總理篩發生器，我轉換爲列表打印，然後打印給定範圍內的素數。我很確定我的對數是正確的，但出於某種原因，我在我的素數列表中得到了一些額外的值，這些值並不是素數。 （我馬上就發現了這個，因爲我輸出的最後一個值是3599，這不是素數）。 我真的不知道，如果我有某種邏輯錯誤，所以任何幫助將是真棒

def sieve(n): 
    a = [True] * (n) 
    a[0] = a[1] = False 
    for (i, isPrime) in enumerate(a): 
     if isPrime: 
       yield i 
      for n in range(i*i, n, i): 
       a[n] = False 


def pairs(li): 
    pair = 0 
    for i, x in enumerate(li): 
     if i < len(li)-1: 
      if li[i] + 2 == li[i+1]: 
       pair += 1 
    return pair 

p_3600 = list(sieve(3600)) 

ans = [vals for vals in p_3600 if vals > 1600] 

print ans 

print "pairs:", pairs(ans) 

Answer 1

你的篩函數不正確。您將所有數字標記爲不是總數，以「2」開頭。 您需要通過這prime*prime

因此，黃金的下一個倍數開始，你必須在i*i不i開始（我用i*2其作品，但就是多餘的，因爲第一循環已經覆蓋時i==2）

def sieve(n): 
    a = [True] * n 
    a[0] = a[1] = False 
    for (i, isPrime) in enumerate(a): 
    if isPrime: 
     yield i 
     for j in range(i*i, n, i): 
      a[j] = False 

來測試你的名單，我建議你添加一個主要的測試，所以你肯定：

# make sure it works: time-costly but reassuring 
import math 
for i in ans: 
    si = int(math.sqrt(i))+1 
    for j in range(2,si): 
     if i%j==0: 
      raise Exception("%d is not prime (%d)" % (i,j))