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

欧拉计划中的第十个问题:



我找到了这个片段:

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

我不明白为什么我的代码(第二个)要慢得多？

最佳答案

您的算法正在分别检查从 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)) (或@Daniel Fischer 评论的 O(n^(3/2) / logn) )，假设除法成本与乘法相同。

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



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