Skip to main content
 首页 » 编程设计

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

2025年05月04日8artech

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

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; 

请您参考如下方法:

如评论中所述,实现埃拉托色尼筛法将是一个更好的选择。它占用 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 个索引。