Eratosthenes 循环筛不能正确拉动元素

Question

我正在使用埃拉托色尼筛法算法，该算法涉及从列表中提取第一个元素，将其添加到素数列表中，然后从原始列表中提取该数字的任何倍数（因此从 2 开始，追加 2，删除 2) 的所有倍数。然后转到下一个数字。

我的循环（在 2-10 列表的测试运行中）第一次做了它应该做的事情，但下次它没有拉 3，而是直接跳到 5，我剩下 2、5 和 9 的列表。这是我的代码。

list_before_primes = [num for num in range(2, usr_in + 1)]
print(list_before_primes)
list_o_primes = []

for element in list_before_primes:
    list_o_primes.append(element)
    for sub_element in list_before_primes:
            if sub_element % element == 0:
                list_before_primes.remove(sub_element)

print(list_o_primes)

Answer 1

由于您在循环内修改了 list_before_primes，因此不应使用 for element in list_before_primes:（如@Kevin 所述）。

您可以改用 while list_before_primes: 并将第一项弹出到 element。

这也将解决@Kashyap Maduri 的评论（因为该元素将从列表中删除）。

顺便说一句，您可以将 list_before_primes = [num for num in range(2, usr_in + 1)] 简化为 list_before_primes = list(range(2, usr_in + 1))

Answer 2

算法实现如下：

def sieve_of_eratosthenes(usr_in):
    #you don't need list comprehension in your implementation. You can do this:
    list_before_primes = range(2, usr_in + 1)
    print(list_before_primes)

    #makes a set of list_before_primes
    #funny things can happen when you modify and iterate over the list at the same time. 
    #it is better to make a copy and remove from it.
    list_o_primes = set(list_before_primes)

    for i,element in enumerate(list_before_primes):
        for sub_element in list_before_primes[i+1:]:
            if sub_element % element == 0:
                if sub_element in list_o_primes:
                    list_o_primes.remove(sub_element)

    print(list_o_primes)

if __name__ == '__main__':
    sieve_of_eratosthenes(10)

Eratosthenes 循环筛不能正确拉动元素

Sieve of Eratosthenes loop not correctly pulling elements

python

sieve-of-eratosthenes