0

这是我的埃拉托色尼筛法，用于查找最大为 n 的素数。我觉得它应该可以工作，但我得到一个错误，我真的不明白为什么：

    mylist.remove(i)
ValueError: list.remove(x): x not in list

为什么会提到 x？

这是代码：

def number_list(n):

    mylist = []
    for i in range(2,n+1):
        mylist.append(i)
    return mylist


def sieve():

    n = eval(input("What is the maximum limit? "))
    mylist = number_list(n)

    primes = []

    for i in mylist:
        p = mylist.pop(0)
        primes.append(p)
        if i % p == 0:
            mylist.remove(i)
    return primes
4

4 回答 4

2

您mylist在迭代它时正在修改。这会产生奇怪的结果。在您的循环的第一次运行期间，i将分配您列表的第一项，即2. 然后，声明

p = mylist.pop(0)

从列表的开头删除这个项目，并且p也设置为2. 接下来，您的支票i % p == 0将 yield True，您尝试i从列表中删除，但它已经消失了，导致您引用的错误消息。

这个循环的完整逻辑似乎被打破了。对于遇到的每个素数，您需要从列表中删除该素数的所有倍数。您通常需要两个嵌套循环来实现这一点。

此外，您的功能

def number_list(n):
    mylist = []
    for i in range(2,n+1):
        mylist.append(i)
    return mylist

相当于

def number_list(n):
    return range(2, n + 1)

即你根本不需要这个功能，只需使用它range(2, n + 1)。

于 2011-03-10T14:02:17.173 回答
1

这是埃拉托色尼筛的工作代码。必须将范围对象制成列表，因为我们需要删除项目。

def all_primes_to(n):
    numbers = list(range(2,n+1))
    primes = []
    while numbers:
        prime = numbers.pop(0)
        primes.append(prime)
        remove_multiples(numbers, prime)
    return primes

def remove_multiples(lst, x):
    length = len(lst)
    i = 0
    while i < length:
        if lst[i] % x == 0:
            del lst[i]
            length -= 1
        i += 1
于 2011-03-10T14:47:14.427 回答
0

不确定，但我认为你不应该修改你正在迭代的列表。
在 perl 中是禁止的，也许在这种情况下 python 是类似的。

另一件事是我会为您的所有项目列表使用生成器。
您正在使用的方法会破坏大'n's的内存。

于 2011-03-10T14:00:27.757 回答
0

这里提到的具体x实际上是i（如上一行所见）。

Stacktraces 通常还会为您提供行号，因此知道这一点应该很容易调试。

无论哪种方式，这里的问题是您多次尝试删除某些项目。您可以使用 a 轻松修复它，if i in mylist但我建议您查看筛子的完整实现，以获得更快/更优化（更重要的是，工作）的版本。它可能会让您对 Python 的工作原理有一些额外的了解。

于 2011-03-10T14:02:21.040 回答