Python中的素数生成器：数字的积累

Question

我的生成器运行得很好：我测试过很多次。只是有个问题：随着数字的增大，程序变得越来越慢。虽然我想到了一个解决办法，但由于我刚开始学习Python不久，所以不知道该怎么做。

我的生成器长这样：

    while 0==0:
        i=input('Enter the number for which all previous shall be tested for primality: ')
        n=0
        a=[0,1,2]
        while n<=i:
            n=n+1
            for b in range(2,n):
                if n%b==0:
                    break
                if b==(n-1):
                    a.append(n)
                    print a`

我发现如果把a=[0,1,2]放到while 0==0之前，它会在程序运行时累积之前使用过的所有数字。我想改变的是，当a累积质数时，它可以用这些质数来追赶下一个未知的数字。比如说，我想要所有小于100的质数。然后，我又想要所有小于200的质数。这样的话，我就不想重新计算小于100的质数，而是希望程序跳过这些，直接从100之后的第一个质数开始。

任何建议都非常感谢，我使用的是Python 2.7。

a = [2,3,5,7,11]
while 1:
    b = input('Enter the number for which all previous shall be tested for primality: ')
    c = len(a)
    d = 0
    isprime = True
    while b<=a[c-1] and not d==c:
            if b==a[d]:
            print a[0:d]
        if d==(c-1) and not b==a[d]:
            break
        d = d + 1
    while b>a[c-1]:
        d = 0
        print a[c-1]
        if b%a[d]==0:
            isprime = False
            break
        while a[d]==a[c-1]:
            f = a[c-1] + 2
            for g in range(f,b,2):
                if b%g==0:
                    isprime = False
                    break
            if isprime:
                a.append(b)
                print a

好的，我让这个程序工作得更好，让它在找到质数时把它们存起来，以便下次找质数时使用。假设我想找小于1000的质数。程序会计算出这些质数。然后，我想知道小于2000的质数。因为程序已经找到了小于1000的质数，所以不需要重新计算。它会把所有小于或等于输入的最大数字的质数拿出来，然后用已知的质数去除新数字，找出剩下的质数。接着，它会把新的质数加到a中，继续进行。

不过，有个问题。它并没有按照我计划的方式工作，我正在努力修复这个问题。也许你们可以帮忙看看哪里出了错？

好的，我已经编辑了代码，让它运行得更快：

While 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=0
    while n<=i:
        n=n+1
        a=int(n**.5)
        for b in range(2,n):
            if n%b==0:
                break
             if b==a:
                print n
                break

到目前为止，这个程序的运行时间比我原来的程序和我尝试过的其他程序都要短。在我进行的一次测试中，我让它和我第一个算法一起找出所有小于100000的质数。我的第一个算法花了大约4分钟，而我的新程序只用了大约1分40秒。可以说是一次很大的升级。

Answer 1

有很多种找素数的方法，其中“筛法”是最快的。如果你知道怎么用 C语言扩展Python，你可以使用 primesieve 这个工具。下面是一个用Python实现的 埃拉托斯特尼筛法 的例子，如果你还有其他问题，随时告诉我：

from __future__ import generators
def eratosthenes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {}  # map composite integers to primes witnessing their compositeness
    q = 2   # first integer to test for primality
    while 1:
        if q not in D:
            yield q        # not marked composite, must be prime
            D[q*q] = [q]   # first multiple of q not already marked
        else:
            for p in D[q]: # move each witness to its next multiple
                D.setdefault(p+q,[]).append(p)
            del D[q]       # no longer need D[q], free memory
        q += 1

Answer 2

这个方法应该会更快：

while 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=5
    a=[2,3]
    while n<=i:
        n=n+1
        isPrime = True
        for b in a:
            if n%b==0:
                isPrime = False
                break
        if isPrime:
            a.append(n)
            print a

不过我觉得除了使用更高级的算法和处理非常大的数字（比如10的100次方），你可能很难让速度比O（看看sebastian的评论）更快。

随着数字变大，速度总是会变慢。