素數與python

Question

我是相當新的編程，我決定做一些練習來提高我的能力。我堅持做一個練習：「找出所有素數低於200萬的總和。」我的代碼太慢了。

起初，我試圖解決作爲一個正常的主要問題，並結束了與此：

sum = 2 + 3 
for i in range (5, 2000000, 2): 
    for j in range (3, i, 2): 
     if i%j == 0: 
      break 
    else: 
     sum += i 
print(sum) 

這樣一來，所有的偶數將會從循環中排除。但它並沒有解決我的問題。這裏的規模真的很大。

所以我試圖理解這段代碼發生了什麼。我在一個循環內部有一個循環，循環內循環運行外部循環時間的索引（不完全是因爲列表不是從0開始的），對吧？所以，當我試圖找到20歲以下的素數時，它會運行8次外部循環，但內部循環60（我不知道這個數學是否正確，正如我所說的，我對編程非常瞭解）。但是當我用2,000,000的時候，我總共運行了999,993,000,012次的內部循環，這是瘋狂的。

我的朋友告訴我，埃拉托色尼的篩，我試圖創建一個新的代碼：

list = [2] 
list.extend(range(3, 2000000, 2)) 
for i in list: 
    for j in list: 
     if j%i == 0 and j > i: 
      list.remove(j) 
print(sum(list)) 

這就是我取得的成績試圖模擬篩（忽略偶數幫助）。它的速度要快得多（對於其他代碼，找到200,000以下的素數需要很長時間，而且我可以做到這一點），但僅僅在合理的時間內計算20億次是不夠的。自從我開始編寫代碼後，代碼就在後臺運行，但仍然沒有任何結果。我不知道這件事情循環了多少次，我現在太累了，現在就想想它。

我來這裏尋求幫助。爲什麼這麼慢？我應該學習/閱讀/做什麼來改進我的代碼？還有其他方法比這個篩更有效嗎？感謝您的時間。

Answer 1

因爲list.remove是O(n)操作，所以您正在做很多操作。而你並沒有表現出真正的篩選，只是變相的嘗試分工;你仍然在做原始代碼中所做的所有剩餘測試。

Eratosthenes的篩子通常使用一組標誌來實現;以最簡單的形式，每個索引對應於相同的數字，並且對於所有索引，該值最初爲True，但是0和1。你迭代，當你找到一個True值時，你將所有指數的倍數設置爲False。這意味着工作是順序添加，而不是乘法，而不是分割（這是更昂貴的。）