在Python中筛选Eratosthenes，寻找一个更简洁和正确的方法来寻找素数

Question

我用Erasothenes筛法开发了一个素数发生器。使用一个列表，我消除了所有2到用户指定数字的倍数，继续使用3，等等。由于p2被无限期地重新分配到列表的第一个元素，我的代码当前给了我一个错误。你知道吗

n = int(input("What are the primes up to this number?"))
soe = []
for i in range (2, n+1):
    soe.append(i)
for i in range (2, n+1):
    if i % 2 == 0:
        soe.remove(i)
    p2 = soe[0]
    holder =1
while p2 < n and holder == 1:
    for i in soe:
        if i % p2 == 0:
            soe.remove(i)
    p2 = soe[0]
print (soe)

Answer 1

@icedtrees答案的一个大的性能改进（至少对于cpython）是在C级使用slice赋值将项设置为零。你知道吗

maxPrime = int(input("What are the primes up to this number?"))
sieve = list(range(maxPrime))
for i in range(2, maxPrime):
    if sieve[i]: # not removed yet = prime!
        print(i)
        sieve[::i] = [0] * len(sieve[::i]) # marked as not prime

你可以用

        sieve[i::i] = [0] * ((len(sieve)-1)//i)

最后一行，如果你愿意的话。你知道吗

我没有尝试过，但是pypy在优化内部for循环方面可能做得很好，与片分配相比。你知道吗