python中2,000,000以下的素数之和

Question

我正在尝试欧拉计划的第 10 题，即 2,000,000 以下所有素数的总和。我尝试过使用 Python 实现埃拉斯托坦筛法，我编写的代码对于 10,000 以下的数字非常有效。

然而，当我尝试求更大数字的素数之和时，代码运行时间太长（求 100,000 以内的素数之和需要 315 秒）。该算法显然需要优化。

是的，我看过这个网站上的其他帖子，比如列出 N 以下所有素数的最快方法，但是那里的解决方案对代码如何工作的解释很少（我仍然是初学者程序员），所以我无法实际上向他们学习。

有人可以帮助我优化我的代码，并清楚地解释它是如何工作的吗？

这是我的代码：

primes_below_number = 2000000 # number to find summation of all primes below number
numbers = (range(1, primes_below_number + 1, 2)) # creates a list excluding even numbers
pos = 0 # index position
sum_of_primes = 0 # total sum
number = numbers[pos]
while number < primes_below_number and pos < len(numbers) - 1:
    pos += 1
    number = numbers[pos] # moves to next prime in list numbers
    sum_of_primes += number # adds prime to total sum
    num = number
    while num < primes_below_number:
        num += number
        if num in numbers[:]:
            numbers.remove(num) # removes multiples of prime found

print sum_of_primes + 2

正如我之前所说，我是编程新手，因此对任何复杂概念的彻底解释将不胜感激。谢谢。

Answer 1

正如您所看到的，有多种方法可以在 Python 中实现埃拉斯托滕筛法，这些方法比您的代码更有效。我不想用花哨的代码让您感到困惑，但我可以展示如何加快您的代码的速度。

首先，搜索列表并不快，从列表中删除元素甚至更慢。然而，Python 提供了一个集合类型，它在执行这两个操作时非常有效（尽管它确实比简单列表消耗更多的 RAM）。令人高兴的是，可以轻松修改代码以使用集合而不是列表。

另一个优化是我们不必一直检查素因数直到，我在下面的代码中将primes_below_number其重命名为。hi只需求 的平方根就足够了hi，因为如果一个数字是合数，则它必须有一个小于或等于其平方根的因子。

我们不需要保存素数之和的运行总和。最好最后使用 Python 的内置sum()函数来完成此操作，该函数以 C 速度运行，因此比以 Python 速度逐一进行加法要快得多。

# number to find summation of all primes below number
hi = 2000000

# create a set excluding even numbers
numbers = set(xrange(3, hi + 1, 2)) 

for number in xrange(3, int(hi ** 0.5) + 1):
    if number not in numbers:
        #number must have been removed because it has a prime factor
        continue

    num = number
    while num < hi:
        num += number
        if num in numbers:
            # Remove multiples of prime found
            numbers.remove(num)

print 2 + sum(numbers)

您应该会发现这段代码在几秒钟内运行；在我的 2GHz 单核机器上大约需要 5 秒。

您会注意到我已经移动了评论，以便它们位于正在评论的行上方。这是 Python 中的首选样式，因为我们更喜欢短行，而且内联注释往往会使代码看起来混乱。

还可以对内部while循环进行另一个小的优化，但我让您自己弄清楚。:)