欧拉项目 #10 (Python)

Question

为什么我求 200 万以下所有素数总和的算法这么慢？我是一个相当初级的程序员，这就是我为寻找解决方案而想出的方法：

import time

sum = 2
start = time.time()

for number in range(3, 2000000):
    prime = True
    for x in range(2, number):
        if number % x == 0:
            prime = False
    if prime:
        sum += number

print "Sum =", sum
end = time.time() - start
print "Runtime =", end

有人可以帮我吗？谢谢！

Answer 1

您的算法使用试除法，这非常慢。更好的算法使用埃拉托斯特尼筛法：

def sumPrimes(n):
    sum, sieve = 0, [True] * n
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

print sumPrimes(2000000)

运行时间应该不到一秒。如果您对使用素数进行编程感兴趣，我会在我的博客上谦虚地推荐这篇文章。

Answer 2

您可以做许多优化（并且应该做，因为您需要素数生成来解决 Euler 项目中的许多问题，因此快速实现可以简化以后的事情）。

看一下阿特金筛（以及相关的筛）（http://en.wikipedia.org/wiki/Sieve_of_Atkin），了解如何通过蛮力加速素数生成（从算法上来说是这样）。

然后看看这篇 SO-post 的精彩答案（列出 N 以下所有素数的最快方法），它记录了许多素数生成算法/实现。