Euler10项目-为什么第一个python代码运行得比第二个快得多？

Question

欧拉计划的第十个问题：

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

我找到了这个片段：

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

已发布here 持续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

第一个版本预先计算范围内的所有素数，并将它们存储在sieve数组中，然后找到解决方案就是在数组中添加素数。它可以看作是memoization的一种形式。

第二个版本测试范围内的每个数字，看看它是否是质数，重复前面计算已经做的大量工作。

总之，第一个版本避免了重新计算值，而第二个版本一次又一次地执行相同的操作。

Answer 2

你的算法是分别检查从2到N（其中N=2000000）的每个数字的素性。

Snippet-1使用了2200年前发现的sieve of Eratosthenes算法。 它不检查每个号码，但：

• 对2到2000000的所有数字进行“筛选”。
• 找到第一个数字（2），将其标记为素数，然后从筛选中删除其所有倍数。
• 然后找到下一个未删除的数字（3），将其标记为素数，并从筛选中删除其所有倍数。
• 然后找到下一个未删除的数字（5），将其标记为素数，并从筛选中删除其所有倍数。
• 。。。
• 直到找到素数1409并从筛子上删除它的所有倍数。
• 然后找到了1414~=sqrt（2000000）的所有素数，它停止了
• 从1415到2000000的数字不需要检查。所有没有被删除的都是素数。

因此该算法产生了N以内的所有素数

注意，它不做任何除法，只做加法（甚至不做乘法运算，而且它对这么小的数并不重要，但对较大的数可能很重要）。时间复杂度是O(n loglogn)，而你的算法有一些接近O(n^(3/2))（或者O(n^(3/2) / logn)，正如@Daniel Fischer评论的那样），假设除法的成本与乘法相同。

来自维基百科（链接在上面）的文章：

Time complexity in the random access machine model is O(n log log n) operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n.

（在这种情况下，n = 2e6）

Answer 3

为了容易理解这种差异，试着想想每个数字将被用作电位分隔器的次数：

在您的解决方案中，当数字2被测试为质数时，它将被测试为每个数字的2。你沿途传递的每一个数字都将被用作下一个数字的电位分频器。

在第一个解决方案中，一旦你跨过一个数字，你就永远不会回头——你总是从你到达的地方往前走。顺便说一句，一种可能的常见的优化方法是只在标记2:

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

这样，您只需查看每个数字一次，并将其所有乘法向前清除，而不是通过所有可能的除法器一次又一次地检查每个数字及其所有前导，并且if语句防止您对以前遇到的数字重复工作。