python之理解 Python 中的埃拉托色尼筛法

我在 python 中找到了一个示例代码，它给出了 n 以内的所有素数，但我就是不明白，为什么它会做它做的事情？

我读过关于 Sieve of Eratosthenes 的维基百科文章但根本不知道这是如何工作的。

pp = 2 
ps = [pp] 
lim = raw_input("Generate prime numbers up to what number? : ") 
while pp < int(lim): 
    pp += 1 
    for a in ps: 
        if pp%a==0: 
            break 
        else: 
            ps.append(pp) 
 
 
print set(ps) 

如能解释循环的工作原理，我们将不胜感激。

编辑 - 发现代码全错了，因为它表示 25 是素数，通过更深入的搜索发现这不是筛子，有人可以显示一个利用 python 中的筛子的生成器并对其进行解释

请您参考如下方法:

由于还没有人展示真正的筛子或解释它，我会尝试。

基本方法是从 2 开始计数并消除 2*2 和所有 2 的更高倍数(即 4、6、8...)，因为它们都不是质数。 3 在第一轮中幸存下来，因此它是质数，现在我们消除 3*3 和所有 3 的更高倍数(即 9、12、15...)。 4 个被淘汰，5 个幸存等等。每个素数的平方是一种优化，它利用了每个新素数的所有较小倍数将在前几轮中被消除这一事实。当您使用此过程计数和消除非素数时，只会留下素数。

这是一个非常简单的版本，注意它不使用模除法或根:

def primes(n): # Sieve of Eratosthenes 
    prime, sieve = [], set() 
    for q in xrange(2, n+1): 
        if q not in sieve: 
            prime.append(q) 
            sieve.update(range(q*q, n+1, q)) 
    return prime 
 
>>> primes(100) 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73 
79, 83, 89, 97] 

上面的简单方法出奇地快，但没有利用素数只能是奇数这一事实。

这是一个基于生成器的版本，它比我发现的任何其他版本都快，但在我的机器上达到 Python 内存限制 n = 10**8。

def pgen(n): # Fastest Eratosthenes generator 
    yield 2 
    sieve = set() 
    for q in xrange(3, n+1, 2): 
        if q not in sieve: 
            yield q 
            sieve.update(range(q*q, n+1, q+q)) 
 
>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10) 
5.987867565927445 

这是一个稍慢但内存效率更高的生成器版本:

def pgen(maxnum): # Sieve of Eratosthenes generator 
    yield 2 
    np_f = {} 
    for q in xrange(3, maxnum+1, 2): 
        f = np_f.pop(q, None) 
        if f: 
            while f != np_f.setdefault(q+f, f): 
                q += f 
        else: 
            yield q 
            np = q*q 
            if np < maxnum: 
                np_f[np] = q+q 
 
>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10) 
7.420101730225724 
 
>>> list(pgen(10)) 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 

要测试一个数字是否为质数，只需执行以下操作:

>>> 539 in pgen(539) 
False 
>>> 541 in pgen(541) 
True 

这里有一些关于这个内存效率更高的版本如何工作的提示。它使用 dict 仅存储最少的信息，即下一个非素数(作为键)及其因子(作为值)。当在 dict 中找到每个非素数时，将其删除并添加具有相同因子值的下一个非素数键。