在Python中給定數字下面的素數總和

Question

我已經寫了下面的代碼塊來計算在這種情況下在一定數量-2000000以下的所有素數的總和，但是這需要相當長的一段時間執行; 20秒：

def summation_of_primes_below_n(n): 
list = [] 
sum = 0 
for i in range(2, n): 
    if checks_if_prime(i) == True: 
     list.append(i) 
return list 
for j in list: 
    sum = sum + j 
return sum 

def checks_if_prime(n): 
    if n == 2: 
     return True 
    import math 
    for i in range(2, math.ceil(math.sqrt(n))+1): 
     if n%i == 0: 
      return False 
     elif i == math.ceil(math.sqrt(n)): 
      return True 

print(summation_of_primes_below_n(2000000)) 

所以我想知道是否有辦法讓我的代碼更有效率。對於同樣的建議，我將不勝感激。此外，我寧願你提供更多的基本解決方案，因爲我是初學者，並提供相同的邏輯。非常感謝！

Answer 1

您可以通過實施一些更好的算法開始。對於如：Sieve of Eratosthenes

或者，如果你很高興與您當前的邏輯，那麼一些優化，可以幫助：

• 檢查只針對單號：只有

  for i in range(3, n, 2):

• 檢查表格號碼6n+1, 6n+5

• 您不需要爲每次迭代檢查：elif i == math.ceil(math.sqrt(n)):。如果控制超出迴路，則數字爲素數

• 您可以將您的check_prime轉換爲generator pattern。可以節省一些冗餘，並可能改善參考的位置。