Python中的基本素数生成器

Question

只想要一些关于我的素数发生器的反馈.例如,它是否正常,它是否用于很多资源等.它不使用库,它相当简单,它反映了我目前的编程技巧状态,所以不要因为我想学习而退缩.

def prime_gen(n):

    primes = [2]
    a = 2 

    while a < n:

        counter = 0 

        for i in primes:
            if a % i == 0:
                counter += 1

        if counter == 0:
            primes.append(a)
        else:
            counter = 0

        a = a + 1

    print primes

Answer 1

有一些常见的优化：

例子：

def prime(x):
    if x in [0, 1]:
        return False
    if x == 2:
        return True
    for n in xrange(3, int(x ** 0.5 + 1)):
        if x % n == 0:
            return False
    return True

• 覆盖基本情况
• 仅迭代至 n 的平方根

上面的示例不生成素数，而是测试它们。您可以对您的代码进行相同的优化:)

我发现用 Python 编写的更有效的算法之一可以在以下问题和答案中找到（使用筛子）：

Python 中的简单质数生成器

我自己对筛选算法的改编：

from itertools import islice


def primes():
    if hasattr(primes, "D"):
        D = primes.D
    else:
        primes.D = D = {}

    def sieve():
        q = 2
        while True:
            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

    return sieve()


print list(islice(primes(), 0, 1000000))

在我的硬件上，我可以很快生成前一百万个素数（假设这是用 Python 编写的）：

prologic@daisy
Thu Apr 23 12:58:37 
~/work/euler
$ time python foo.py > primes.txt

real    0m19.664s
user    0m19.453s
sys 0m0.241s

prologic@daisy
Thu Apr 23 12:59:01 
~/work/euler
$ du -h primes.txt
8.9M    primes.txt