在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

我用这个：

def eras(n):
    last = n + 1
    sieve = [0, 0] + list(range(2, last))
    sqn = int(round(n ** 0.5))
    it = (i for i in xrange(2, sqn + 1) if sieve[i])
    for i in it:
        sieve[i * i:last:i] = [0] * (n // i - i + 1)
    return filter(None, sieve)

真正的魔力在于for-loop中的片分配。它一次性地将非素数从i * i归零到n。你知道吗

Answer 2

@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循环方面可能做得很好，与片分配相比。你知道吗

Answer 3

下面是一个简单而快速的Python筛生成器：

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)
        for product in range(i, maxPrime, i): # gets i*n for all n up to i*n > maxPrime
            sieve[product] = 0 # marked as not prime

代码中的问题是总是分配p2=soe[0]。此外，在最后，当您已经从soe中删除了所有内容时，您将打印soe。你知道吗

您应该打印您使用的每个新p2，包括2，并在soe为空时结束程序。你知道吗

这是您正在运行的修改程序，带有注释：

n = int(input("What are the primes up to this number?"))
soe = []
for i in range (2, n+1):
    soe.append(i)
# you can progress straight into sieving out numbers!
while p2 < n and soe: # stop when your list is empty!
    p2 = soe[0]
    print(p2)
    for i in soe:
        if i % p2 == 0:
            soe.remove(i)
# print (soe) # it's going to be empty at the end