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

你的算法是分别检查从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）