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

首先，搜索列表的速度并不快，而从列表中删除元素的速度甚至更慢。但是，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 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

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

An answer on a recent python sieve question使用此实现python样式。事实证明，很多人都使用了筛子，或者他们认为是筛子的东西，然后开始问为什么它很慢。 ：P如果您需要更多的阅读材料，请查看其中一些相关问题的工具条。

查找包含表示数字是否在集合中的布尔值的元素很容易而且非常快。 array[i]是一个布尔值，如果i在集合中，则为true；否则为false。只需添加一个地址，即可直接从i计算内存地址。

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

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

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

---

一个问题：Why is Sieve of Eratosthenes more efficient than the simple "dumb" algorithm?有许多与筛子相关的好链接。 This one in particular对此进行了很好的讨论，而不仅仅是文字。 （不要在意它是在谈论看起来像筛子的普通Haskell实现，但实际上不是这样。他们在图中将其称为“不忠实”的筛子，依此类推。）

discussion on that question提出了这样的观点，对于某些用途，尝试分割可能比大筛快，因为清除每个质数的所有倍数的位会以不友好的缓存模式占用大量内存。如今，CPU比内存快得多。

Answer 6