被困在项目欧拉 # 10

Question

我对算法非常陌生，不久前才开始编写代码。请用this problem from Project Euler帮助我：

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

我试着阅读了关于Sieve算法的知识，并在理解了这个概念之后实现了它。你知道吗

def SieveofEratosthenes(n):
    prime = [True for i in range(n+1)]
    p = 2
    while(p*p <= n):
        if(prime[p] == True):
            for i in range(p*p, n+1, p):
                prime[i] = False
        p+=1 
        for p in range(2, n):
            if prime[p]:
                print(p),

#Driver Program
if __name__=='__main__':
    n=2000000
    print('Following are the prime numbers smaller than or equal to', n)
    SieveofEratosthenes(n)

问题是时间太长了。在我的机器上花了7.8秒。 加上我怎么把这些数字加起来？有什么更好的方法处理它？你知道吗

Answer 1

以下是您的答案：

def SieveofEratosthenes(n):
    prime = [True for i in range(n+1)]
    p = 2
    while p*p <= n:
        if prime[p]:
            for i in range(p*p, n+1, p):
                prime[i] = False
        p += 1
    return prime


#Driver Program
if __name__=='__main__':
    n = 2000000
    print('Following is the sum of the prime numbers smaller than or equal to', n)
    primes = SieveofEratosthenes(n)
    sum_all = sum(p for p in range(2, n) if primes[p])
    print(sum_all)

它提示：

>>> Following is the sum of the prime numbers smaller than or equal to 2000000
>>> 142913828922

一些评论

• 以后尝试拆分功能：一个用于获取素数的函数，另一个用于打印。你知道吗
• 在python中，if foo == True可以像if foo一样编写