为什么我的埃拉托色尼筛法这么慢？

Question

我正在解决 Project 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 循环和一轮过滤重写它，它运行得更快。新代码：

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

运行 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 log(log(n))，所以筛具有渐近时间复杂度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 ]等，我们有如下近似递归：

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 值的总和成正比，直到 numbers 为空。我没有分析该系列的行为，但计算表明增长比 O(n*log(log(n))) 差得多。（编辑：我在撰写此答案时没有想到的 analysis 说它是 O((n/log(n))^2).)

为什么我的埃拉托色尼筛法这么慢？

Why is my Sieve of Eratosthenes so slow?

python

algorithm

performance

primes

time-complexity