了解Python中Eratosthenes的筛选器

Question

我在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的发电机和解释它

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添加到素数列表中。

线pp%a==0基本上是说“上，当a除以pp的remander是零”，即a分pp和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 

这不是最有效的筛选（更有效率的在for n in range(2*i, lim, i):行中执行操作，但它会起作用，并且isPrime[i]将是true if i是prime。

Answer 3

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

但是，以上代码的工作原理如下。

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. 了存储在ps和素数的列表此for循环迭代检查，目前的数量，pp是这些数字中的任何一个整除，如果是，那么这个数是不是素数和primeFlag设置为False和我们打破了内部for循环。
5. 如果数量没有任何之前的素数整除，那么它必须是一个素数，因此，变量primeFlag是True和if声明追加列表ps与pp。

Answer 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 

下面是一些提示，以这种更高效的内存版本如何工作。它使用dict来存储最小的信息，下一个非素数（作为关键字）及其因子（作为值）。由于在dict中找到每个非素数，因此将其删除，并使用相同的因子值添加下一个非主键。