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

Question

我在python上写了这段代码来解决项目欧拉问题＃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返回，一旦你发现，一个数字是复合的。

其次，你不想检查偶数。与xrange(3,2000000, 2)

三跳过他们，就没有必要从2检查所有的数字都在nprime，因为a*b = b*a

由于您使用Python 2我把它换成range与xrange，这将是一点点更高效。

Answer 2

如果你想要所有的素数直到2000000，你应该考虑使用Eratosthenes的筛。

代码在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