优化Python中的素数生成器

Question

我在寻找一些建议，想要优化我的质数生成器。能不能请你们在回复中包含一些修正建议，并简单解释一下为什么这样做会更快呢？

def primeList ( highestNumber ):
""" This function takes a integer and returns a list of all primes less than or equal to that integer"""

    numbers = range( 2, highestNumber + 1 ) # creates an inclusive list of all numbers between 2 and highestNumber
    isPrime = [ True ] * len( numbers ) # each element corresponds to an element in numbers and keeps track of whether or not it is prime
    primes = [] # Where I'll build a list of prime numbers

    for i in range( len( numbers )  ):
        if ( isPrime[i] == True ):
            increment = numbers[i]
            position = i + increment
            primes.append( numbers[ i ] )

            while ( position < len( numbers )): # will only execute if the above if statement is true because position will still be greater than len( number )
                isPrime[position] = False  # Sets an element of isPrime to False if it is a multiple of a lower number
                position += increment   
    return primes

Answer 1

def primeList ( highestNumber ):
    """ This function takes a integer and returns a list of """
    """ all primes less than or equal to that integer"""

    numbers = range( 3, highestNumber + 1, 2 ) 
    isPrime = [ True ] * len( numbers ) 
    primes = [2] if highestNumber >= 2 else []

    for number in numbers:
        if ( isPrime[(number-3)/2] ):
            increment = number
            position = (number * number - 3) / 2

            if ( position >= len( numbers )):
                primes += (x for x in numbers[(number-3)/2:] 
                             if isPrime[(x-3)/2])
                # primes += (2*i+3 for i in xrange((number-3)/2,
                #                   len(numbers)) if isPrime[i])
                break
            else:
                primes.append( number )
                while ( position < len( numbers )): 
                    isPrime[position] = False  
                    position += increment   
    return primes

只处理奇数会更快，而且占用的空间更少。

我们可以开始从 n*n 中去掉 n 的倍数，因为对于任何 n*k，只要 k < n，我们都有 n*k = k*n，也就是说，它会被标记为 k 的倍数。

一旦平方数超过上限，我们就可以停止了——到那时，所有的倍数已经在 isPrime 列表中标记过了。

Answer 2

计算质数最简单的方法是使用一种叫做“筛法”的工具，这个方法是由古希腊数学家埃拉托斯特尼在两千多年前发明的：

def primes(n):
    sieve = [True] * (n+1)
    ps = []
    for p in range(2,n):
        if sieve[p]:
            for i in range(p*p, n, p):
                sieve[i] = False
            ps.append(p)
    return ps

虽然还有更快的计算质数的方法，但如果你不知道你的应用程序是否真的需要比上面提到的函数更快，或者你的内存不够用来存储筛法所需的数据，那么你就应该使用这个简单的方法，因为它不容易出错。如果你想了解更多关于埃拉托斯特尼筛法的内容，我推荐你看看我博客上的一篇文章，标题是用质数编程。

Answer 3

你可以把“numbers”列表中大于2的偶数去掉，因为这些偶数肯定不是质数，所以你不用检查它们。你可以通过设置range函数的步长参数来实现这一点。

Answer 4

这里已经有一个很棒的讨论，关于各种生成质数的方法，链接在这里：在N以下列出所有质数的最快方法

在那个链接里，有一个Python脚本，你可以用它来和其他几种算法进行比较。