Python3在迭代时从列表中删除元素（Eratosthenes筛）

Question

我正在构建一个程序，使用python的Eratosthenes筛算法来寻找所有小于n的素数。 该算法首先创建一个从2到n的数字列表，然后遍历该列表，删除第一个可用元素和相应的倍数。问题是我这样做似乎没有得到正确的结果。我也会很感激任何建议，以提高性能。你知道吗

算法如下：

def primes(max):
    '''The sieve of Eratosthenes
    Algorithm to find all primes smaller than max'''
    init = time.clock()
    allNum = [a for a in range(2, max+1)]
    primes = []
    for n in allNum:
        # remove all multiples of prime n
        toRemove = (a for a in range(n, max+1, n) if a in allNum)
        for i in toRemove:
            print('toRemove:', i)
            allNum.remove(i)
        # add the prime to the list
        primes.append(n)

    deltaT = time.clock() - init
    print('Time taken to process:', deltaT)
    return primes

（解决）我就是这样改变的：

while len(allNum) != 0:
    prime = allNum[0]
    # remove all multiples of prime
    toRemove = (a for a in range(prime, max+1, prime) if a in allNum)
    for i in toRemove:
        print('toRemove:', i)
        allNum.remove(i)
    # add the prime to the list
    primes.append(prime)

Answer 1

另一种更快的方法是建立一个布尔值列表（全部为真）并使用该算法将它们设置为假。素数是列表中保持为真的所有索引：

def primes(max):
    mask = [True for i in range(0,max + 1)]
    for num in range(2,max):
        if not mask[num]:
            continue
        for multiple in range(num*2, max+1, num):
            mask[multiple] = False
    primes = [i for i,mask_value in enumerate(mask) if mask_value]
    return primes[2:]

Answer 2

迭代列表时，引用的是每个偏移量，而不是每个值。例如，当您得到第一个结果时，如果它限定并删除该值，则所有后续值都将向前滑动，并且偏移量将递增。偏移量现在是索引1（基0）。但你刚刚删除了索引0，所有东西都向前滑动了。你基本上跳过了第二个数字。你知道吗

0$ python3
Python 3.4.8 (default, Mar 23 2018, 10:04:27)
[GCC 4.8.5 20150623 (Red Hat 4.8.5-16)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [a for a in range(1, 20)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> the_list = [a for a in range(1, 20)]
>>> for a in the_list:
...     the_list.remove(a)
...
>>> the_list
[2, 4, 6, 8, 10, 12, 14, 16, 18]
>>>

Answer 3

我不相信你可以改变一个列表，因为你迭代它。你知道吗

您可以切换到while循环，只要原始列表中还有任何数字，该循环就会运行。对于每一次迭代，你至少要删除第一个数字：如果它是素数，你就把它移到素数列表中；如果不是素数，你就删除它和它的所有倍数。你知道吗