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

Question

项目欧拉的第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

您的算法分别从2到N(其中N = 2000000)检查每个数字的素数.

Snippet-1使用了大约2200年前发现的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评论),假设分割成本与乘法相同.

来自维基百科(上面链接)的文章:

随机访问机器模型中的时间复杂度是O(n log log n)运算,这是泛素系列渐近逼近的直接结果log log n.

(n = 2e6在这种情况下)