欧拉计划 #10 (Python) [英] Project Euler #10 (Python)

问题描述

为什么我的算法找出所有小于 200 万的素数之和这么慢?我是一个相当初级的程序员，这就是我想出的解决方案:

Why is my algorithm for finding the sum of all prime numbers below 2 million so slow? I'm a fairly beginner programmer and this is what I came up with for finding the solution:

import time

sum = 2
start = time.time()

for number in range(3, 2000000):
    prime = True
    for x in range(2, number):
        if number % x == 0:
            prime = False
    if prime:
        sum += number

print "Sum =", sum
end = time.time() - start
print "Runtime =", end

有人可以帮我吗?谢谢！

Can someone please help me out? Thanks!

推荐答案

你的算法使用了试除法，非常慢.更好的算法使用埃拉托色尼筛法:

Your algorithm uses trial division, which is very slow. A better algorithm uses the Sieve of Eratosthenes:

def sumPrimes(n):
    sum, sieve = 0, [True] * n
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

print sumPrimes(2000000)

这应该会在不到一秒的时间内运行.如果您对使用质数编程感兴趣，我在我的博客中谦虚地推荐这篇essay.

That should run in less than a second. If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.

这篇关于欧拉计划 #10 (Python)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！