Eratosthenes算法Sieve实现中的若干问题

Question

这是项目euler中的第十个问题，在这个问题中，我们应该找到小于200万的所有质数的和。我正在使用Eratosthenes算法的筛子来寻找素数。现在我面临着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

因此，这里可以进行各种改进：

首先，由于Eratosthenes筛子的性质，您可以用for i in range(2,int(limit**0.5)+1):替换for i in range(2,limit):，数组将正常计算，但速度要快得多；但是，结果是，您必须稍后对数字求和。

此外，您不能读取每个素数，也不会想要读取每个素数；相反，您只需要程序告诉您里程碑，例如每次程序达到某个数字时，就可以检查所有内容。

您的程序似乎没有考虑到数组从0开始的事实，这肯定会导致一些问题；但是，这应该是相当可以修复的。

最后，我发现您的程序似乎将1算作质数；这应该是另一个简单的修复方法。