用 Python 理解埃拉托斯特尼筛法

Question

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

我读过关于埃拉托斯特尼筛法的维基百科文章，但根本不知道它是如何工作的。

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 中的筛子的生成器并解释它

Answer 1

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

基本方法是从 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]

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

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

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

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