素数的生成器函数

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

Eratosthenes筛选:最有效的素数生成器算法

取自这里:

Python中的简单Prime生成器 - 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 2

你需要重新设置prime，以True作为而块内的第一条语句，而不是之前它。事实上，一旦你击中一个合数，prime就永远不会再次成立，所以你永远不会产生更多的数字。