Python 3 - 迭代时从列表中删除元素（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

我认为您无法在遍历列表时更改它。

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

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

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

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:]

Python 3 - 迭代时从列表中删除元素（Eratosthenes 筛法）

Python 3 - removing elements from a list while iterating (sieve of Eratosthenes)

python

primes