为什么我的Eratosthenes筛子这么慢？

Question

我在Project Euler上解决了一些问题,并且必须生成200万个素数以解决问题.我对Eratosthenes筛子的实施结果非常缓慢,但我不知道为什么.有人可以解释一下这个实现的主要问题.我觉得它太漂亮了,然后我发现它非常可怕:(.我在网上发现了它的另一个实现,它比我的快得多.

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

Eratosthenes的筛子看起来像这样:

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.这个总和是log(log(n)),所以筛子具有渐近时间复杂度O(n*log(log(n))),假设算术是恒定时间.这真的很好.

你的功能不会这样做.无论它是否可被整除,你filter都可以遍历每一个元素.每个元素都被处理为每个素数直到分割它的第一个素数,并且处理素数p去除了大约1/p的元素.让素数序列为p [0],p [1],p [2]等,并使大小序列为n [0],n [1],n [2]等,我们有以下近似的重复:numbersprimenumbersnumbers

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))).