生成素数的生成器函数

Question

我正在尝试写一个生成器函数，用来打印质数，代码如下：

 def getPrimes(n):
    prime=True
    i=2
    while(i<n):
        for a in range(2,i):
            if(i%a==0):
                prime=False
                break
        if(prime):    
            yield i

但是我得到的结果并不是我想要的。调用 p=getPrimes(100) 应该给我一个生成器函数，这个函数能从2到100之间遍历质数，但我得到的结果却只有 [2,3]。我哪里出错了呢？

Answer 1

正如Istvan Chung所说，你的问题在于你没有重置你的prime标志。不过，我建议你不直接修复这个问题，而是考虑一个替代方案。

与其使用一个标志变量来检测你是否在循环中没有遇到break而完成了整个循环，不如在循环后面加一个else块：

def getPrimes(n):
    i = 2
    while i < n :
        for a in range(2, i):
            if i % a == 0:
                break
        else:    
            yield i

如果循环正常完成，else块会被执行，而不是因为break语句提前停止。

你可能还可以进一步改进，只测试质数因子，而不是所有小于i的整数。下面是一个使用递归的方法（另一种方法是保持一个之前计算过的质数列表，但如果n非常大，这可能需要占用很多存储空间）：

def getPrimes(n):
    yield 2
    i = 3
    while i < n:
        for a in getPrimes(int(math.sqrt(i))+1):
            if i % a == 0:
                break
        else:
            yield i
        i += 2

Answer 2

在编程中，有时候我们需要把一些数据从一个地方传到另一个地方。这个过程就像是把水从一个水壶倒到另一个水壶一样。我们可以用不同的方法来实现这个过程，比如使用变量、函数或者其他工具。

在这个过程中，可能会遇到一些问题，比如数据不匹配或者格式不对。这就像是你想把热水倒进一个冷水壶，结果发现壶的口太小，水倒不进去。为了避免这些问题，我们需要提前检查数据，确保它们是可以顺利传输的。

总之，数据传输是编程中很重要的一部分，理解它的基本概念可以帮助我们更好地处理程序中的各种情况。

def isprime(n):
    for i in range(2 ,int((n**0.5))+1):
        if n % i == 0:
            return False
    return True

def getPrimes(n):
    yield 2
    i = 1
    while i <= n-2:
        i += 2
        if isprime(i):
            yield i

Answer 3

你有几个错误，看看评论部分：

def getPrimes(n):
    i = 2
    while i < n :
        prime = True # reset the `prime` variable before the inner loop
        for a in xrange(2, i):
            if i%a == 0:
                prime = False
                break
        if prime:    
            yield i
        i += 1 # don't forget to advance `i`

现在我们来看看一个更好的实现方式，它能正确处理边界情况，减少很多循环次数，并生成小于n参数的所有质数序列：

def getPrimes(n):
    if n <= 2:
        raise StopIteration
    yield 2
    for i in xrange(3, n, 2):
        for x in xrange(3, int(i**0.5)+2, 2):
            if not i % x:
                break
        else:
            yield i

无论如何，这段代码的运行效果是符合预期的：

[x for x in getPrimes(20)]
=> [2, 3, 5, 7, 11, 13, 17, 19]

Answer 4

埃拉托斯特尼筛法：最有效的质数生成算法

摘自这里：

Python中的简单质数生成器 - 由Eli Bendersky提供的答案。

这个方法会把所有2、3、5、7和11的倍数都标记掉。剩下的就是质数。

def genprimes(limit): # derived from 
                      # Code by David Eppstein, UC Irvine, 28 Feb 2002
    D = {}            # http://code.activestate.com/recipes/117119/
    q = 2

    while q <= limit:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

p = genprimes(100)
prms = [i for i in p]

print prms

输出结果：

[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]

Answer 5

你需要在循环的开始部分，把 prime 重新设置为 True，而不是在循环之前。现在的情况是，一旦你遇到一个合成数（也就是不是质数的数），prime 就再也不会变成真了，这样你就不会再得到任何质数了。