에라토스테네스 체 알고리즘을 구현할 때의 문제

Question

이것은 프로젝트의 오일러에서 10 번째 문제입니다.이 문제는 2 백만 이하의 소수를 모두 합한 것입니다. 나는 Saw 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에서 시작한다는 사실을 고려하지 않은 것으로 보이므로 확실히 문제가 발생합니다. 그러나 이것은 상당히 고칠 수 있어야합니다.

마지막으로, 귀하의 프로그램이 소수로 간주되는 것으로 보입니다. 그러나 이것은 또 다른 쉬운 수정이어야합니다.