我需要一些幫助來解釋下面的埃拉托色尼篩法。我從其他一些 Stackoverflow 頁面復制了它，但我不明白它一行一行。有人可以解釋一下嗎？
def eratosthenes(n):
multiples = []
for i in range(2, n):
if i not in multiples:
print (i)
for j in range(i*i, n, i): #Troubled Part
multiples.append(j)
eratosthenes(100)
我特別沒有得到 range(i*i...) 部分。為什么一組括號中有三個屬性？另外，為什么我是平方？謝謝！
uj5u.com熱心網友回復：
讓我們一行一行地進行：
multiples = [] 制作一個合數串列，我們稍后會在這里添加
for i in range (2,n) 我們從 2 到 n 回圈，試圖得到所有的素數。
if i not in multiples我們正在檢查是否i是我們已經找到的合數
print(i)那么i一定是素數，所以讓我們列印出來
for j in range(i*i,n,i)按is計數，從i*i到n，因為這些數字中的每一個都是合數。請注意，我們從 開始i*i，因為i*[number<i]之前的迭代中已經記錄了類似的數字
multiples.append(j)添加j到合數串列中
uj5u.com熱心網友回復：
范圍中的第三個屬性只是一個增量。它是說將 i 添加到 i*i 直到我們達到 n。
因此，隨著我們前進，Eratosthenes 的篩選通過去除素數的倍數（即復合物，在倍數串列中跟蹤）來作業，例如 [2,4,6,8,...], [3,9 ,12,...],[5,25,30,...] 隨著我們繼續。
在上面每個序列的第一個中，我們有素數，序列中的后續元素添加到倍數串列中
您突出顯示的部分：
for j in range(i*i, n, i): #Troubled Part
multiples.append(j)
這只是將質數的所有合倍數相加。為了更明確，讓我們看一下 2。
2 不是倍數。所以它被列印出來。那我們具體想想接下來會發生什么：
for j in range(2*2, 100, 2)
這會將 4、6、8、10 等添加到倍數串列中，我們忽略這些數字，因為它們是合數。您可以將 i*i 簡單地視為我們開始的倍數序列中的下一個元素。
這樣，我們繼續 3，從 9、12、15 等開始。
請注意，合數 4,6,8 在第一次迭代中已經被排除，所以我們可以從 9 開始并繼續。
這其實是傅瑞恩指出的一個重要點。
所以用最清楚的術語來說：
- 2 已列印。倍數串列更新為所有其他偶數 [4,6,8,10,...]
- 我們接下來去 3，因為它不是倍數。我們將 [9,12,15,18,21,...] 添加到串列中。
- 請注意，我們不需要費心將 6 添加到串列中，因為在我們之前考慮 2 時它已經添加了。這就是為什么我們不需要做類似的事情
for j in range(i*2, n, i)
- 這個程序繼續，我們的下一個數字是 5，所以 [25,30,35,40,...] 被添加到倍數
最終只列印素數。
uj5u.com熱心網友回復：
multiples正在存盤一個素數的所有倍數，例如，對于 2 是素4,6,8,10,12...數，則不是素數的倍數，并且沒有必要檢查這些 no，因為它們是否是素數，因為我們知道它們不是。
if i not in multiple表明那i是素數，然后我們保存了 i 的所有倍數。在您的解決方案中，我認為沒有必要使用i*iin for j in range(i*i, n , i) 但2*i將是正確的選擇，即for j in range(2*i, n, i)并且multiples應該是型別setnotlist因為這將允許重復并且搜索時間復雜度將O(N)在串列案例和O(1)設定案例中。
def eratosthenes(n):
multiples = set()
for i in range(2, n):
if i not in multiples:
print (i)
for j in range(2*i, n, i): #Troubled Part
multiples.add(j)
eratosthenes(100)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/396032.html
上一篇：leetcode-472-連接詞