如何使Eratosthenes的篩子更快？

Question

我想解決項目歐拉中的10個問題。它包括找到所有素數低於200萬的總和。我根據Eratosthenes的Sieve編寫了以下代碼。

import time 
t0 = time.time() 
n=200000 
liste=list(range(2,n)) 
k=2 
s=2 
while k <=n: 
    liste=list(set(liste)-set(range(k,n,k))) 
    if liste!=[]: 
     k=min(liste) 
     s+=k 
    else: 
     break 
print(s) 
t1 = time.time() 
total = t1-t0 
print(total) 

我測試了上面的代碼n = 200000，但它對於n = 2000000太慢了。我非常感謝能夠幫助改善這個計劃。

Answer 1

總是嘗試在幾個範圍內測量代碼的empirical complexity。

您的代碼很慢，因爲您發現設置的差異，並且您總是在設置和列表之間進行轉換並返回。你應該自始至終都使用一個設置，並與

sete.difference_update(range(p*p,n,p*2)) 

更新它的地方找到的最小元素，你可以叫min(sete)上設定，無需轉換列表。由於對最小元素的低效搜索，所得代碼的總體複雜度將接近n^1.5，這不是太明亮，但也不太可怕。尤其是，它在ideone.com上的4.9秒內完成，找到200,000以下素數的總和，以及400,000的0.5秒（僅在首次使用賠率時進行了額外的優化）。

Answer 2

爲了找到低於200000的素數總和，下面的代碼（使用eratosthenes篩選）工作得更快，您的代碼需要將近55secs，而下面的代碼只需要0.8secs來執行！

import time 
t0 = time.time() 
n = 200000 
sieve = [True] * (n + 1) 
for i in range(2, n + 1) : 
    if sieve[i] : 
    for mult in range(i + i, n + 1, i) : 
     sieve[mult] = False 
s=0  
for i in range(2,n + 1): 
    if sieve[i] : 
     s+=i  
print(s) 
t1 = time.time() 
total = t1-t0 
print(total)