數據結構 - 表

Question

這是作業，但教訓給了我答案了。我無法將答案中的單詞放入代碼行

#Calculate all the primes below 1000 

    result = [1] 
    candidates = range(3, 1000) 
    base = 2 
    product = base 

    while candidates: 
     while product < 1000: 
      if product in candidates: 
       candidates.remove(product) 
      product = product + base 
     result.append(base) 
     base = candidates[0] 
     product = base 
     del candidates[0] 

    result.append(base) 
    print result 

這是「Erastothenes的篩」的一個版本。

這是在給我的解釋。

在這個例子中的新東西......

內置的功能範圍實際上返回，可以像所有其他列表中使用的列表。 （它包含第一個索引，但不包含最後一個索引。）列表可以用作邏輯變量。如果它不是空的，那麼它是真的 - 如果它是空的，那麼它是假的。因此，儘管候選人的意思是「雖然名單上的候選人不是空的」，或者只是「在仍有候選人的時候」。你可以編寫someList中的someElement來檢查一個元素是否在列表中。你可以寫someList.remove（someElement）從someList中刪除someElement。您可以使用someList.append（something）將一個元素附加到列表中。實際上，你也可以使用+（比如someList = someList + [something]），但效率不高。您可以通過給數字（其中第一個元素，奇怪的是，是元素0）括號內的列表的名稱後，它的位置在列表的元素得到。因此someList [3]是someList的第四個元素。 （關於下面的更多內容。）您可以使用關鍵字del刪除變量。它也可以用來（如這裏）從列表中刪除元素。因此，del someList [0]刪除someList的第一個元素。如果刪除前的列表是[1,2,3]，那麼之後會是[2,3]。

纔去到解釋索引列表元素的奧祕，我會給例子的簡要說明。

這就是所謂的「Erastothenes的篩」古算法（或東西接近）的一個版本。它考慮候選號碼的集合（或在這種情況下，列表），然後系統地刪除已知不是質數的數字。我們怎麼知道？因爲它們是另外兩個數字的產物。

我們從包含數字[2..999]的候選者列表開始 - 我們知道1是一個素數（實際上，它可能也可能不是，取決於你問誰），並且我們想要所有素數在下面1000.（實際上，我們的候選人名單是[3..999]，但2名也是候選人，因爲它是我們的第一個基地）。我們也有一個名爲result的列表，它總是包含迄今爲止的更新結果。首先，這個列表只包含數字1.我們也有一個名爲base的變量。對於算法的每次迭代（「循環」），我們刪除這個基數（它總是最小的候選）的所有數字。每次迭代之後，我們知道剩下的最小數是一個素數（因爲所有小數的產物都被刪除 - 得到它？）。因此，我們將它添加到結果中，將新基數設置爲該數字，並將其從候選列表中刪除（因此我們不會再處理它）。當候選列表爲空時，結果列表將包含所有素數。聰明吧？

我不明白的是，他們說，「我們刪除此基數的某一倍數的所有數字。」代碼行在哪裏？有人可以一行一行地解釋程序在做什麼嗎？我試圖理解每行代碼的原理以及原因。感謝您的幫助。

Answer 1

在每個while candidates:循環的開始處，product等於base。然後在那個循環中你有另一個循環，while products < 1000。在此循環結束時，您通過base增加product。所以product經歷base的每個倍數。然後刪除product的所有值，這是您「刪除基數的倍數」的地方。

基本上什麼程序做的是：

... 
set product to base 

for each candidate 
    for each multiple of base, referred to as 'product' 
     remove product from candidates 
    set base to new value 
    reset product to new base 
    ...