python - 改进 Euler #10 上的运行时间

Question

因此，我正在攻克一个在小规模上看起来非常简单的欧拉问题，但一旦我将其提高到我应该做的数字，代码就需要永远运行。这是问题:

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

Find the sum of all the primes below two million.

我是用 Python 做的。我可以等待几个小时让代码运行，但我宁愿找到一种更有效的方法来解决这个问题。这是我用 Python 编写的代码:

x = 1;
total = 0;

while x <= 2000000:
    y = 1;
    z = 0;
    
    while x >= y:    
        if x % y == 0:
            z += 1;   
        
        y += 1;
            
    if z == 2:
        total += x
    
    x += 1;
            
print total;

Answer 1

如评论中所述，实现埃拉托色尼筛法将是一个更好的选择。它占用 O(n) 额外空间，在本例中是一个长度约为 200 万的数组。它还在 O(n) 中运行，这在天文数字上比您在 O(n²) 中运行的实现快。

我最初是用 JavaScript 写的，所以请耐心等待我的 python:

max = 2000000    # we only need to check the first 2 million numbers
numbers = []
sum = 0

for i in range(2, max):    # 0 and 1 are not primes
    numbers.append(i)      # fill our blank list
for p in range(2, max):
    if numbers[p - 2] != -1:   # if p (our array stays at 2, not 0) is not -1
        # it is prime, so add it to our sum              
        sum += numbers[p - 2]
        # now, we need to mark every multiple of p as composite, starting at 2p
        c = 2 * p
        while c < max:
            # we'll mark composite numbers as -1
            numbers[c - 2] = -1
            # increment the count to 3p, 4p, 5p, ... np
            c += p

print(sum)

这里唯一令人困惑的部分可能是我为什么使用 numbers[p - 2]。那是因为我跳过了 0 和 1，这意味着 2 在索引 0 处。换句话说，所有内容都向旁边移动了 2 个索引。