Python 埃拉托斯特尼筛法算法优化

Question

我正在尝试实现埃拉托斯特尼筛法。输出结果看起来是正确的（只是少了一个“2”，需要加上），但是如果输入的数大于10万左右，似乎会花费很长时间。有什么方法可以优化这个函数吗？

def sieveErato(n):
     numberList = range(3,n,2)

     for item in range(int(math.sqrt(len(numberList)))):
            divisor = numberList[item]
            for thing in numberList:
                    if(thing % divisor == 0) and thing != divisor:
                            numberList.remove(thing)
    return numberList

Answer 1

你可以试试古希腊数学家埃拉托斯特尼的方法。首先，准备一个包含你想检查的所有数字的列表，按从小到大的顺序排列。然后，从数字2开始，给它标记一下。接着，把列表中每隔一个数字都划掉，直到列表的末尾。然后，去看数字3，给它也标记一下。之后，把列表中每隔三个数字的也划掉。接着看数字4，发现它已经被划掉了，所以跳过它。对每一个还没有被划掉的数字都重复这个过程。

最后，留下的被标记的数字就是质数。这个方法比较快，但有时候会占用很多内存。你可以稍微优化一下，先把所有的偶数都去掉（因为它们不是质数），然后手动把2加到列表里。这样会稍微改变一下逻辑，但能节省一半的内存。

这里有个图示可以帮助你理解我说的内容： http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

这段代码用来生成小于1000万的质数，运行需要2秒钟。

def erat_sieve(bound):
    if bound < 2:
        return []
    max_ndx = (bound - 1) // 2
    sieve = [True] * (max_ndx + 1)
    #loop up to square root
    for ndx in range(int(bound ** 0.5) // 2):
        # check for prime
        if sieve[ndx]:
            # unmark all odd multiples of the prime
            num = ndx * 2 + 3
            sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
    # translate into numbers
    return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]

Answer 3

你的算法并不是埃拉托斯特尼筛法。你使用的是试除法（也就是取余运算），而不是像埃拉托斯特尼在两千多年前那样划掉倍数。这里有关于真正筛选算法的解释，下面是我简单明了的实现，它会返回不超过n的素数列表：

def sieve(n):
    m = (n-1) // 2
    b = [True]*m
    i,p,ps = 0,3,[2]
    while p*p < n:
        if b[i]:
            ps.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i+=1; p+=2
    while i < m:
        if b[i]:
            ps.append(p)
        i+=1; p+=2
    return ps

我们只对奇数进行筛选，筛选的范围到n的平方根为止。对于j的那些看起来奇怪的计算，它们在被筛选的整数3、5、7、9等和b数组中的索引0、1、2、3等之间建立了对应关系。

你可以在http://ideone.com/YTaMB上看到这个函数的实际运行，它能在不到一秒的时间内计算出一百万以内的素数。