项目欧拉 #10

1 投票

4 回答

783 浏览

数据工程师

提问于 2025-04-18 04:13

我刚开始接触算法，几周前才开始编程。请帮我解决这个问题：

小于10的质数的和是2 + 3 + 5 + 7 = 17。

请找出小于两百万的所有质数的和。

我尝试了常规的方法，但效果很差。我试着了解筛选算法，并实现了这个算法，结果它只对奇数有效：

i=[x for x in range(3,2000001,2)]
print(len(i))
j=0
sum=2
while(max(i)!=j):
    m=0
    while(m<(2000000-(i[j]**2)/(2*i[j]))):
        a=(i[j]**2)+2*m*i[j] 
        if a in i:
            i.remove(a)
        m+=1
    j+=1
for s in range(1,len(i)+1):
    sum+=i[s]
print(sum)

这个程序运行了超过5个小时。我在3个小时的时候就停了。请问我哪里出错了？

性能优化数学计算算法编程质数筛选算法

4 个回答

根据@jonrsharpe提供的代码，可以做一个改进 - 把 for multiple in range(2, (max_//number)+1): 替换成 for multiple in range(number, (max_//number)+1):

def prime_sieve2(max_):
        primes = list(range(max_+1))
        primes[1] = 0 
        for number in primes:
                if number:
                        # starting from number rather than 2 
                        for multiple in range(number, (max_//number)+1): 
                                primes[number * multiple] = 0 
        return primes

在改进之前的评估步骤（你可以看到从2到number的平方的评估是可以省略的）：

check 2, 4, 6, 8, 10, 12, 14,...
check 3, 6, 9, 12, 15, 18, 21,...  (6 is already checked by '2')
check 5, 10, 15, 20, 25, 30, 35,...  (10, 15, 20 are already checked by '2' and '3')
check 7, 14, 21, 28, 35, 42, 49, 56,... (again, 14, 21, 28, 35, 42 are redundant checked)

改进后的评估步骤：

check 4, 6, 8, 10, 12, 14,...
check 9, 12, 15, 18, 21,...
check 25, 30, 35, ...
check 49, 56, ...

回答于 2025-04-18 由 Python大师

分享举报

我之前也遇到过同样的问题，花了两个通宵才搞定。

后来，我看了马克·皮尔格林的《DIVE INTO PYTHON》，里面有一章讲生成器函数的内容，我用这个技巧解决了我的问题。下面是可以解决这个问题的生成器函数：

def prime(max):

    for n in range(2,max):

        for x in range(2,int(n**0.5) + 1):

            if n%x == 0:


                break
        else:

            yield n

接下来，写一个叫做sum的函数来调用这个生成器函数，可以在命令行或者这个程序里调用。我是在命令行里调用的，但这样做能解决你的问题。

祝你好运！:)

回答于 2025-04-18 由 Python大师

分享举报

这个筛法是个不错的方法，但你的实现有点让人困惑，而且显然没有正确工作。考虑一下这个非常简单（没有优化过的）实现：

def prime_sieve(max_):
    """Create a list containing all prime numbers equal to or less than max_."""
    primes = list(range(max_+1)) # all numbers 0 to max_
    primes[1] = 0 # 1 is not prime
    for number in primes: # iterate through all numbers
        if number: # if not 0 (i.e. prime)
            for multiple in range(2, (max_ // number) + 1):
                primes[number * multiple] = 0 # set multiples to zero
    return primes

虽然可以做得更高效，但在我的机器上，对于 max_ == 2000000 的情况，大约运行两秒钟。

一般来说，使用 for 循环比 while 循环更适合用来遍历像列表这样的容器。另外，我在列表中保留了非素数的位置，但把它们设置为零——否则索引（你代码中的 i[j]）会出问题。

对于测试示例：

>>> prime_sieve(10)
[0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0]
>>> list(filter(None, prime_sieve(10)))
[2, 3, 5, 7]
>>> sum(prime_sieve(10))
17

回答于 2025-04-18 由 Python大师

分享举报

看起来你在努力学习，所以我不会给你完整的解决方案，只会给你一些方向。

不要随便操作列表，比如往里面加东西、拿东西出来，或者检查某个元素是否在里面。这会让你的代码变得很慢。相反，应该保持一个已知的质数列表。
写注释。我看了你的代码好几分钟，完全不知道它在干嘛。
在合适的时候使用 math 函数。比如 math.sqrt 比用 **0.5 快大约30%。
这一段代码： for s in range(1,len(i)+1): sum+=i[s] 看起来很糟糕。你可以直接用 sum(i) 来计算列表的总和。
[x for x in range(3,2000001,2)] 和 range(3,2000001,2)（在Python2中）或者 list(range(3,2000001,2))（在Python3中）是完全一样的。
不要用 i、a、m 这样的变量名，它们的意思不清楚。

你怎么知道一个数字是不是质数呢？你可以检查所有比它小的质数，看它们是否能整除这个数字。如果没有一个能整除，就把它保存下来。实际上，你只需要检查那些小于你数字平方根的质数。

如果你想用内存换取速度，可以直接使用 @vamosrafa 的函数，执行 sum(prime(2e6))。在Python2中，把 range 改成 xrange。这样你只需要在内存中保存几个数字，但会进行很多不必要的除法运算（如果一个数字不能被3或5整除，那它也不会被15整除）。

回答于 2025-04-18 由 Python大师

分享举报

项目欧拉 #10

4 个回答

撰写回答