エラトステネス篩アルゴリズムの実装の問題

Question

これは、プロジェクト・オイラーの10番目の問題です。この問題では、200万未満の素数の合計を求めることになっています。私は素数を見つけるためにSag of Eratosthenesアルゴリズムを使用しています。今、私は直面しており、Sieve of Eratosthenesアルゴリズムのパフォーマンスに問題があります。

print(i,"",sum_of_prime)がループ内にあると、パフォーマンスが大幅に低下します。それが動作し、パフォーマンスを維持するためにとにかくありますか？これが従来の方法で行われた場合は、結果を得るまでに約13分かかります。

#Euler 10 

#Problem: 
#The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. 
#Find the sum of all the primes below two million. 

#Author: Kshithij Iyer 
#Date of creation: 15/1/2017 

import time 
#Recording start time of the program 
start=time.time() 
def sum_of_prime_numbers(limit): 
    "A function to get the sum prime numbers till the limit" 
    #Variable to store the sum of prime numbers 
    sum_of_prime=0 
    #Sieve of Eratosthenes algorithm 
    sieve=[True]*limit 
    for i in range(2,limit): 
     if sieve[i]: 
      sum_of_prime=sum_of_prime+i 
      for j in range(i*i,limit,i): 
       sieve[j]=False 
      print(i,"",sum_of_prime) 
    print("The sum of all the prime numbers below",limit,"is",sum_of_prime) 
    return 
#sum_of_prime_numbers(10) 
sum_of_prime_numbers(2000001) 
print("Execution time of program is",time.time()-start) 

#Note: 
#I did give the conventioanl method a try but it didn't work well and was taking 
#some 13 minutes to get the results. 

#Algorithm for reference 
#Input: an integer n > 1 

#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. 

Answer 1

だからここに作ることができる様々な改良がある

：

まず、原因エラトステネスふるいの性質のためには、あなたはfor i in range(2,int(limit**0.5)+1):でfor i in range(2,limit):を置き換えることができ、アレイが正常に計算されますが、はるかに高速になります;しかし、その結果、後で数字を合計する必要があります。

また、すべてのプライムを読むことはできませんし、あなたもしたいと思いません。代わりに、プログラムが特定の番号に達するたびにマイルストーンを伝えるプログラムが必要です。

あなたのプログラムは、配列が0から始まるという事実を考慮していないようです。しかし、これはかなり修正可能でなければなりません。

最後に、あなたのプログラムはプライムとして1をカウントするように見えます。これはもう一つの簡単な修正であるはずです。