如何讓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