200万未満のすべての素数の合計を計算するコードが長すぎる

Question

コードは、nの値が小さい場合に実行される処理を行いますが、200万未満のすべての素数の合計を計算したいと思います。このコードでは無限の時間がかかるようです。私はPyScripterで働いています。このコードをより効率的にする方法はありますか？

def is_prime(a): 
    return all(a % i for i in range(2, a)) 

def sum_of_primes(n): 
    sum = 0 
    x = 2 
    while x < n: 
     if is_prime(x): 
      sum = sum + x 
     x = x+1 
return sum 

def main(): 
    print(sum_of_primes(2000000)) 

if __name__ == '__main__': 
    main() 

Answer 1

Sieve of Eratosthenesは、いくつかの数値以下のすべての素数を見つける最良のアルゴリズムの1つです。

基本的には、範囲2のサイズのブール値のリストを任意の数に作成します。次に、各真値インデックスのすべてのインデックスを削除します。あなたが2に遭遇したリストを検索し始めた後、2 * nのすべてのインデックスをfalseに更新した場合、3にジャンプして3つのインデックスをすべてfalseに更新します。それからあなたは既にそれを偽に更新したので、4をスキップします。次に5に来て5 * nをすべてfalseに置き換えます。終了します。そして、真の価値のあるすべてのインデックスが素数であるという長いリストが得られます。このリストは、必要に応じて使用できます。ウィキペディアで指摘したように

基本的なアルゴリズムは次のようになります。

Let A be an array of Boolean values, indexed by integers 2 to n, 
initially all set to true.  

for i = 2, 3, 4, ..., not exceeding √n: 
if A[i] is true: 
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n: 
     A[j] := false.  
Output: all i such that A[i] is true.