数据结构 - 表

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 
    ...