python 中小于 2,000,000 的素数之和

Question

我正在尝试欧拉计划的第 10 题，这是 2,000,000 以下所有素数的总和。我已经尝试使用 Python 实现 Erasthotenes 筛法，我编写的代码对于 10,000 以下的数字非常有效。

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

是的，我看过这个网站上的其他帖子，比如 Fastest way to list all primes below 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

尝试使用 numpy，应该会更快。用xrange替换range，可能对你有帮助。

Answer 2

首先，从列表中删除数字会非常慢。而不是这个，列一个列表

primes = primes_below_number * True
primes[0] = False
primes[1] = False

现在在你的循环中，当你找到素数 p 时，将所有合适的 k 的 primes[k*p] 更改为 False。（你实际上不会做乘法，当然你会不断地添加 p。）

最后，

primes = [n for n i range(primes_below_number) if primes[n]]

这应该会快很多。

其次，一旦找到大于 primes_below_number 的平方根的素数，就可以停止查找，因为合数必须具有不超过其平方根的素数因子。

Answer 3

如您所见，在 Python 中有多种方法可以比您的代码更有效地实施 Erasthotenes 筛法。我不想用花哨的代码让您感到困惑，但我可以展示如何稍微加快您的代码速度。

首先，搜索列表并不快，从列表中删除元素更慢。然而，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 循环进行的小优化，但我让你自己想办法。 :)

Answer 4

这是对您的代码的优化：

import itertools

primes_below_number = 2000000
numbers = list(range(3, primes_below_number, 2))
pos = 0

while pos < len(numbers) - 1:
    number = numbers[pos]
    numbers = list(
        itertools.chain(
            itertools.islice(numbers, 0, pos + 1),
            itertools.ifilter(
                lambda n: n % number != 0,
                itertools.islice(numbers, pos + 1, len(numbers))
            )
        )
    )
    pos += 1

sum_of_primes = sum(numbers) + 2
print sum_of_primes

这里优化是因为：

将总和移到循环外。
我们可以创建另一个列表而不是从列表中删除元素，内存在这里不是问题（我希望）。
创建新列表时，我们通过链接两个部分来创建它，第一部分是当前数字之前的所有内容（我们已经检查过），第二部分是当前数字之后的所有内容，但前提是它们不是能被当前数整除。
使用 itertools 可以使事情变得更快，因为我们将使用迭代器而不是多次循环遍历整个列表。

另一种解决方案是不删除列表的某些部分，而是像@saulspatz 所说的那样禁用它们。

这是我能找到的最快方法：http://www.wolframalpha.com/input/?i=sum+of+all+primes+below+2+million

更新

这是布尔方法：

import itertools

primes_below_number = 2000000
numbers = [v % 2 != 0 for v in xrange(primes_below_number)]
numbers[0] = False
numbers[1] = False
numbers[2] = True

number = 3

while number < primes_below_number:
    n = number * 3  # We already excluded even numbers
    while n < primes_below_number:
        numbers[n] = False
        n += number
    number += 1
    while number < primes_below_number and not numbers[number]:
        number += 1

sum_of_numbers = sum(itertools.imap(lambda index_n: index_n[1] and index_n[0] or 0, enumerate(numbers)))

print(sum_of_numbers)

这在几秒钟内执行（在我的 2.4GHz 机器上用了 3 秒）。

Answer 5

您可以存储布尔值数组，而不是存储数字列表。这种位图的使用可以被认为是实现集合的一种方式，它适用于密集集合（成员值之间没有大的差距）。

使用此实现 python 风格。事实证明，很多人已经实现了筛子，或者他们认为是筛子的东西，然后就来问为什么它很慢。 :P 如果您想阅读更多内容，请查看其中一些的相关问题侧边栏 material。

查找包含表示数字是否在集合中的布尔值的元素非常简单且速度极快。 array[i] 是一个布尔值，如果 i 在集合中则为真，否则为假。内存地址可以直接从 i 中通过一次加法计算出来。

（我掩盖了这样一个事实，即布尔数组可能会为每个元素存储一个完整的字节，而不是将每一位用于不同元素的更有效的实现。任何像样的筛子都会使用位图。)

从集合中删除一个数字就像设置 array[i] = false 一样简单，无论先前的值如何。没有搜索，没有比较，没有跟踪发生的事情，只有一次记忆操作。（好吧，两个位图：加载旧字节，清除正确的位，存储它。内存是字节可寻址的，但不是位可寻址的。）

基于位图的筛子的一个简单优化是甚至不存储偶数字节，因为只有一个偶数素数，我们可以对其进行特殊处理以将内存密度加倍。然后 i 的会员身份保存在 array[i/2] 中。（除以二的幂对计算机来说很容易。其他值要慢得多。）

一个SO问题： Why is Sieve of Eratosthenes more efficient than the simple "dumb" algorithm? has many links to good stuff about the sieve. This one in particular 有一些很好的讨论，用文字而不是代码。（没关系，它谈论的是一个看起来像筛子但实际上不是的常见 Haskell 实现。他们在图表中称其为 "unfaithful" 筛子，依此类推。）

discussion on that question 提出了这样一个观点，即对于某些用途，试验除法可能比大筛法更快，因为清除每个素数的所有倍数的位会以缓存不友好的模式触及大量内存。现在 CPU 比内存快得多。

python 中小于 2,000,000 的素数之和

Sum of primes below 2,000,000 in python

python

optimization

primes

更新