python - Python 中的基本素数生成器

Question

只是想要一些关于我的素数生成器的反馈。例如可以吗，占用资源多吗等等。它不使用任何库，相当简单，它反射(reflect)了我目前的编程技能水平，所以不要犹豫，因为我想学习。

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 编写的更有效的算法之一是在以下问题和答案中找到的(使用筛子):

Simple Prime Generator in 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