Project Euler 10 - 为什么第一个Python代码运行比第二个快？

Question

这是Project Euler的第10个问题：

10以下的质数加起来是2 + 3 + 5 + 7 = 17。

现在要找出200万以下所有质数的总和。

我找到了这个代码片段：

sieve = [True] * 2000000 # Sieve is faster for 2M primes
def mark(sieve, x):
    for i in xrange(x+x, len(sieve), x):
        sieve[i] = False

for x in xrange(2, int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve, x)

print sum(i for i in xrange(2, len(sieve)) if sieve[i]) 

发布在这里，运行时间为3秒。

我写了这个代码：

def isprime(n):
    for x in xrange(3, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

sum=0;
for i in xrange(1,int(2e6),2):
    if isprime(i):
        sum += i

我不明白为什么我的代码（第二个）运行得这么慢？

Answer 1

正如Óscar的回答所指出的，你的算法重复了很多工作。为了更清楚地看到另一个算法节省了多少处理时间，我们可以看看下面这个修改过的mark()和isprime()函数，它们会记录函数被调用的次数和for循环的总迭代次数：

calls, count = 0, 0
def mark(sieve, x):
    global calls, count
    calls += 1
    for i in xrange(x+x, len(sieve), x):
        count += 1
        sieve[i] = False

运行第一个代码后，我们可以看到mark()被调用了223次，for循环的总迭代次数达到了4,489,006（大约450万）次。

calls, count = 0
def isprime(n):
    global calls, count
    calls += 1
    for x in xrange(3, int(n**0.5)+1):
        count += 1
        if n % x == 0:
            return False
    return True

如果我们对你的代码做类似的修改，就会发现isprime()被调用了1,000,000（100万）次，for循环的迭代次数达到了177,492,735（大约1775万）次。

统计函数调用和循环迭代次数并不总是能明确说明为什么一个算法更快，但一般来说，步骤越少，所需时间就越短。显然，你的代码可以进行一些优化，以减少步骤的数量。

Answer 2

第一种版本会提前计算出范围内所有的质数，并把它们存储在一个叫做sieve的数组里。这样，找到答案就变得简单了，只需要把数组里的质数加起来就行。这种方法可以看作是一种记忆化技术，简单来说就是把计算结果存起来，以后用的时候直接拿出来。

第二种版本则是对范围内的每个数字进行检查，看看它是不是质数。这种做法会重复很多之前已经计算过的工作。

总的来说，第一种版本避免了重复计算，而第二种版本则是一次又一次地做同样的事情。

Answer 3

你的算法是逐个检查从2到N（N=2000000）之间的每个数字，看它们是否是质数。

Snippet-1使用的是埃拉托斯特尼筛法，这个算法大约在2200年前就被发现了。它并不是检查每个数字，而是：

• 先创建一个从2到2000000的“筛子”。
• 找到第一个数字（2），把它标记为质数，然后把它的所有倍数从筛子中删除。
• 接着找到下一个未被删除的数字（3），把它标记为质数，并删除它的所有倍数。
• 然后找到下一个未被删除的数字（5），同样标记为质数并删除它的所有倍数。
• ...
• 直到找到质数1409，并删除它的所有倍数。
• 这样，所有小于等于1414（大约是2000000的平方根）的质数都找到了，算法就停止了。
• 从1415到2000000之间的数字就不需要再检查了，所有没有被删除的数字也是质数。

所以这个算法可以生成所有小于等于N的质数。

注意，它不进行任何除法运算，只进行加法（甚至没有乘法，虽然对于这么小的数字来说这没什么影响，但对于更大的数字可能会有影响）。这个算法的时间复杂度是O(n loglogn)，而你的算法的复杂度大约是O(n^(3/2))（或者O(n^(3/2) / logn)，正如@Daniel Fischer评论的那样），假设除法和乘法的计算成本是一样的。

根据上面链接的维基百科文章：

在随机访问机器模型中，时间复杂度是O(n log log n)操作，这是因为质数调和级数渐近地接近log log n。

（在这个例子中n = 2e6）