为什么我筛厄拉多塞这么慢？

Question

我正在解决欧拉项目的一些问题，必须生成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

编辑：感谢所有的答案！结论是过滤器是问题所在，因为它会遍历每个元素（而不仅仅是那些被标记为非素数的元素），而且每次都会创建一个新列表。用旧的循环和一轮过滤重写它，它的工作速度要快得多。新代码：

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

for i in xrange(len(numbers)):
    if(numbers[i] != 0):
        for j in xrange(i+numbers[i],len(numbers),numbers[i]):
            numbers[j] = 0

primes = filter(lambda x: x,numbers)
return primes

Answer 1

运行 c配置文件显示大部分时间都花在筛选器中。将筛选器替换为列表理解可将速度加快约 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的素数的倒数之和。这个和大约是< code>log(log(n))，所以假设算术是常数时间，则筛子具有渐近时间复杂度< code > O(n * log(log(n))。这真的很好。

你的函数不会这样做。您的过滤器遍历numbers中的每个元素，而不管它是否可以被 numbers元素。让素数序列为p[0]、p[1]、p[2]等，让 数的大小序列为n[0]、n[1]、n[2]等，我们得到以下近似递推： 元素，直到第一个素数将其分开为止，处理素数p会删除大约1>

n[0] = upperBound - 1
n[1] = n[0] * (p[0]-1)/p[0]
n[2] = n[1] * (p[1]-1)/p[1]
...
n[k+1] = n[k] * (p[k]-1)/p[k]

你的算法需要的时间大致与n值的总和成正比，直到数字为空。我没有分析该系列的行为，但计算显示增长比O（n*log（log（n）））差得多。（编辑：我在编写这个答案时没有想到的分析说是O（（n/log（n））^2）。）