1

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

我已经阅读了有关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 中的筛子的生成器并解释它

4

4 回答 4

4

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

基本方法是从 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，将其删除并添加具有相同因子值的下一个非素数键。

于 2013-10-17T00:28:46.160 回答
2

首先，这不是筛子。

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

该行pp%a==0基本上是在说“pp除以时的余a数为零”，即除以a非素数。pppp

这一直持续到我们检查的数字大于我们设置的某个上限（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

这不是最有效的筛子（效率更高的筛子在for n in range(2*i, lim, i):生产线中做事，但它会起作用，并且如果是素数，isPrime[i]它将是正确的。i

于 2013-06-26T13:15:56.790 回答
1

上面的实现会产生错误的答案。我对代码做了一些更改。

但是，上面的代码是这样工作的。

pp = 2
ps = [pp]

我们知道第一个素数是 2，因此，我们生成一个仅包含数字的列表2。

lim = raw_input("Generate prime numbers up to what number? : ")

上面的行从用户那里得到一个输入，这给了我们要生成的素数的上限。

while pp < int(lim):    # 1
      pp += 1           # 2
      primeFlag = True  # 3
      for a in ps:      # 4
          if pp%a==0:
             primeFlag = False
          break
      if primeFlag:     # 5
          ps.append(pp)

编号的行执行以下操作。

  1. 运行一个循环，直到达到上限。
  2. 将pp变量增加 1。
  3. 设置一个标志变量，用于测试数字是否为素数。
  4. 该for循环遍历存储在其中的素数列表ps并检查当前数字pp是否可以被这些数字中的任何一个整除，如果是，则该数字不是素数并且primeFlag设置为False，然后我们跳出内部for循环。
  5. 如果该数字不能被它之前的任何素数整除，那么它一定是素数，因此，变量primeFlagisTrue并且if语句在列表后面ps加上pp。
于 2013-06-26T13:27:50.550 回答
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
于 2013-06-26T15:34:41.030 回答