Python质数生成器yield与return的区别

Question

在搜索Python的素数生成器时，我发现：

def primes(n): 
    if n==2: return [2]
    elif n<2: return []
    s=range(3,n+1,2)
    mroot = n ** 0.5
    half=(n+1)/2-1
    i=0
    m=3
    while m <= mroot:
        if s[i]:
            j=(m*m-3)/2
            s[j]=0
            while j<half:
                s[j]=0
                j+=m
        i=i+1
        m=2*i+3
    return [2]+[x for x in s if x]

print primes(13)
print primes(3000)

并且：

def get_primes(number):
    while True:
        if is_prime(number): #is_prime is defined somewhere else
            yield number
        number += 1

什么更有效，返回列表或yield命令？为什么？考虑我正在寻找大量的质数，例如前1000个素数。顺便说一下，第二段代码似乎是一个无限循环，如何停止它？

谢谢，并抱歉问了这么多问题。

- Nacib Neme

---

这两种方法根本无法比较；一种方法是遍历所有可能的数字并测试每个数字，而另一种方法更为高效，通过实施筛法来完成。你现在在比较苹果和梨。 - Martijn Pieters

Answer 1

这取决于您想对质数列表做什么。首先，如Martijn所指出的那样，第一个算法是一个相当聪明的质数筛选器，而第二个则测试每个质数。如果您对快速素数算法感兴趣，可以查找几种不同的素数筛以更好地理解方法。最简单的是埃拉托色尼筛法。

无论如何，我不认为这是您的问题。您真正寻找的是普通Python函数和生成器之间的区别。在SO上有很多问题和大量文档可以很好地解释生成器是什么。

当我查看您的问题时，侧边栏中出现了这个，我想这会很有帮助。或者只需搜索“generator”文档即可。

简单来说，您的第一个函数返回了一个小于n的素数列表。一旦您拥有了该列表，您可以在需要时访问其中的任何成员，对整个列表调用函数等。第二种方法是生成器。它不返回列表--它返回一个按需生成下一个素数的迭代器。因此，如果您需要逐个按顺序获取质数，以便对每个质数调用函数，那么迭代器可能很好。但是，如果您需要按需访问质数，则无法做到这一点。

如果您正在寻找满足某些条件的第一个素数，那么生成器很好，因为您不必指定范围。如果您只需要前100个素数，没有理由生成前1000个素数。

例如：

for prime in get_primes(2):
    if meets_condition(prime):
        return prime

将会比以下更好：

primeList = primes(1000)
for prime in primeList:
    if meets_condition(prime):
        return prime

如果n很小，但是如果n接近1000，则不是。

我得走了，抱歉。稍后我会扩展和校对这个内容。查找生成器和质数筛！

如果您正在解决projecteuler.com问题，我猜筛子会更好用。

- vroomfondel