了解蟒蛇中埃拉托斯特尼的筛子

Question

我在python中找到了一个示例代码，它给出了直到< code>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)

请解释一下循环是如何工作的。

EDIT-发现代码都错了，因为它表示25为素数，通过更深入的搜索发现这不是筛子，有人能展示一个利用python中筛子的生成器并解释它吗

Answer 1

该代码是使用试验除法来生成一系列素数的尝试。

要纠正它，请执行以下操作：

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:                # unindent
        ps.append(pp)    #  this

为了使它更有效（事实上，是最佳的）试验部门：

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 a*a > pp:         # stop
            ps.append(pp)    #  early
            break
        if pp%a==0:
            break

Answer 2

首先，这不是筛子。

这就是它的工作原理。pp 是我们要测试的数字。在 while 循环的每次迭代中，我们遍历所有已知的素数 （ps） 并检查它们是否除以 pp。如果其中一个这样做，pp不是素数，我们移动到下一个数字。否则，我们在继续之前将pp添加到素数列表中。

行< code>pp%a==0基本上是说“< code>pp除以< code>a的余数为零”，即< code>a除以< code>pp，并且< code>pp不是质数。

直到我们检查的数字大于我们设置的上限（lim）

[编辑:这是筛子]

isPrime = [True for i in range(lim)]
isPrime[0] = False
isPrime[1] = False

for i in range(lim):
    if isPrime[i]:
        for n in range(2*i, lim, i):
            isPrime[n] = False

这不是最有效的筛选(更有效的是在< code>for n in range(2*i，lim，i):行中做事情)，但它将工作，并且< code>isPrime[i]将为真当< code>i是素数时。

Answer 3

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

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

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