为什么 Project Euler 的问题 10 需要这么长时间才能显示输出？

Question

我在 Python 中写了一些代码来解决 Project Euler 的问题 10：'Find the sum of all the primes below two million'。我的代码有效，但不是最佳的。显示输出需要很多时间。

当我尝试解决 20000 以下素数的问题时，它起作用了。当我将它更改为 200 000 或 200 万时，它不会显示输出，它只是在计算，这会花费很多时间，而我预计它会更快，因为计算并不太难。我从来没有输出过。它几乎看起来像是一个无限循环。有谁知道问题出在哪里？

这是我的代码：

answer = 0
for number in range (2, 2000000):  
    if number > 1:  
        for i in range (2, number):  
            if number % i == 0:  
                break  
        else:  
            answer += number
print(answer)

Answer 1

如评论中所述，尝试更快的算法，例如 Sieve of Eratosthenes:

answer = 0
n = 2_000_000
sieve = set()
for x in range(2, n + 1):
    if x not in sieve:
        answer += x
        sieve.update(range(x * x, n + 1, x))
print(answer)

用法：

$ time python sieve.py
142913828922
python sieve.py  0.34s user 0.03s system 98% cpu 0.376 total

@Bakuriu 建议的更好版本：

answer = 0
n = 2_000_000
# Add 2 the only even prime number.
answer += 2
sieve = set()
# Check only odd numbers.
for x in range(3, n + 1, 2):
    if x not in sieve:
        answer += x
        sieve.update(range(x * x, n + 1, 2 * x))
print(answer)

用法：

$ time python sieve_better.py
142913828922
python sieve_better.py  0.19s user 0.02s system 98% cpu 0.211 total

为什么 Project Euler 的问题 10 需要这么长时间才能显示输出？

Why does it take so long to show the output of problem 10 of Project Euler?

python

primes