4

Searching for python prime numbers generator, I found:

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)

and also:

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

What's more efficient, return a list or the yield command? Why? Consider I'm looking for a very large amount of primes numbers, like first 1000 primes. By the way, the second code seems to be an infinite loop, how to stop it?

Thanks and sorry for so many questions.

4

1 回答 1

4

这实际上取决于您想对素数列表做什么。

首先，正如 Martijn 指出的那样，第一个算法是一个非常聪明的素数筛，第二个算法测试每个素数。如果您对快速素数算法感兴趣，我会查找一些不同的素数筛以尝试更好地理解该方法。最简单的是埃拉托色尼筛。

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

当我查看您的问题时，这出现在侧边栏中，我想这会有所帮助。或者只是在文档中搜索“生成器”。

快速解释是，您的第一个函数返回最多为 n 的素数列表。获得该列表后，您可以在需要时访问其中的任何成员，调用整个列表上的函数等。第二种方法是生成器。它不会返回一个列表——它会返回一个迭代器，它会根据需要提供下一个素数。因此，如果您一次需要一个素数，为了可能对每个素数调用一个函数，迭代器可能会很好。但是，如果您需要按需访问素数，则不会这样做。

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

例如：

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 的问题，我会继续猜测筛子会更好地工作。

于 2013-07-01T02:08:19.427 回答