如何使 python 运行上的这段代码更快？

Question

我在 python 上写了这段代码来解决项目 Euler 问题 #10，但我已经等了 15 分钟（运行这段代码）但它仍然没有结束。

请帮我改进或优化这段代码。

这是片段：

def prime (n):
  f = 1 #flag
  for i in range(2,n):
    if n % i == 0:
        f = 0
  return f

s = 0 # Sum
for i in range(2,2000000):
if prime(i) == 1:
    s = i  +  s
print s

Answer 1

import math

def prime (n):
    for i in xrange(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

s = 2 # Sum
for i in xrange(3,2000000, 2):
    if prime(i):
        s += i
print s

对我来说它运行不到 10 秒。

首先，一旦发现数字是合数，您想从 prime return。

其次，您不想检查偶数。使用 xrange(3,2000000, 2)

跳过它们

第三，不需要检查prime中2到n的所有数字，因为a*b = b*a

因为你用的是Python2，所以我把range换成xrange，效率会高一点。

Answer 2

如果您想要所有素数直到 2000000，您应该考虑使用 埃拉托色尼筛法。

python 中的代码：-

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

print(list(eratosthenes2(2000000)))

来源 - http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

如何使 python 运行上的这段代码更快？

how to make this code on python run faster?

python

performance

helpers

如何使 python 运行 上的这段代码更快？

how to make this code on python run faster?

python

performance

helpers

如何使 python 运行上的这段代码更快？