为什么我的埃拉托斯提尼筛得这么慢？

Question

我正在解决Euler项目上的一些问题，并且必须生成200万个素数来解决一个问题。我对埃拉托斯泰尼的筛分实施得非常缓慢，但我不太清楚原因。有人能解释一下这个实现的主要问题吗。我觉得它很漂亮，后来我发现它太可怕了：（。我在网上找到了另一个实现，它比我的要快得多。在

def generatePrimes(upperBound):
    numbers = range(2,upperBound+1)
    primes = []

    while numbers:
        prime = numbers[0]
        primes.append(prime)
        numbers = filter((lambda x: x%prime),numbers)
    return primes

编辑：谢谢大家的回答！由此得出的结论是，过滤器是问题所在，因为它会遍历每个元素（而不是只标记为非质数的元素），而且每次都会创建一个新的列表。重新编写它与良好的旧for循环和一轮过滤，它工作得更快。新代码：

^{pr2}$

Answer 1

运行cProfile表明大部分时间都花在过滤器中。将过滤器替换为列表理解可以将速度提高大约2倍。在

numbers = [n for n in numbers if n%prime != 0]

但这并不能真正解决主要的问题，即每次迭代都要重新创建数字列表，而且速度很慢。更快的实现http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d只是 用0或类似的符号代替非素数。在

Answer 2

埃拉托斯泰尼的筛子是这样的：

def sieve(n):
    primality_flags = [True]*(n+1)
    primality_flags[0] = primality_flags[1] = False
    primes = []
    for i, flag in enumerate(primality_flags):
        if flag:
            primes.append(i)
            for j in xrange(2*i, n+1, i):
                primality_flags[i] = False
    return primes

当外循环到达每个数时，它处理一次，并对每个除以它的素数处理一次。大约1/2个数可被2整除，约1/3可被3整除，依此类推；渐近地讲，每个数被处理的平均次数是1+素数的倒数之和，直到n.This sum is about ^{}，所以这个筛子具有渐近时间复杂度O(n*log(log(n)))，假设算术为常数时间。这真的很好。在

---

你的功能不会这么做。您的filter遍历numbers中的每个元素，而不管它是否可以被prime整除。对每个素数处理每个元素，直到第一个素数将其分开，并且对素数p的处理将除去numbers元素的大约1/p。设素数序列为p[0]、p[1]、p[2]等，并设numbers的大小序列为n[0]、n[1]、n[2]等，我们得到如下近似的递归：

^{pr2}$

您的算法所花费的时间大致与n值的和成正比，直到numbers为空。我还没有分析这个系列的行为，但是计算表明增长比O(n*log(log(n)))糟糕得多。（编辑：一个analysis我在写这个答案时没有想到它是O（（n/log（n））^2）。）