试图解决Project Euler#10，但是代码需要*很多*时间来显示输出

Question

欧拉计划问题10：

低于10的素数之和为2 3 5 7=17。

求200万以下所有素数之和。

我认为我的代码中没有任何错误。但给出答案确实需要很多时间。我尝试过使用PyPy，因为我听说它比CPython解释器快，但仍然不行。

代码如下：

#Implementation of Sieve of Eratosthenes
def prime_sieve(limit):
    primes = range(2, limit)
    for i in primes:
        for j in range(2, primes[-1]):
            try:
                primes.remove(i*j)
            except ValueError:
                pass

    return primes;


answer = 0

for x in prime_sieve(2000000):
    answer += x

print "Answer: %d." % answer
raw_input()

Answer 1

一个更有效的想法是这样的：

你从列表开始：

[0,1,2,3,4,5,6,7,8,9,10]

您希望将每个非素数元素都设置为0，并保留素数。

将0和1设置为零，因为它们不是素数。从现在起，您需要执行以下两个步骤：

1） 找到你还没有考虑过的最小素数，我们称之为n

2）设置每个第n个元素为0（但不是n），因为它们是n的倍数

例如：将0和1设置为0s后：

[0,0,2,3,4,5,6,7,8,9,10]

您没有考虑的最小素数是2，因此您将每秒钟的元素设置为零（但不是2）：

[0,0,2,3,0,5,0,7,0,9,0]

您没有考虑的最小素数是3，所以您将每三个元素设置为零（但不是3），以此类推...：

[0,0,2,3,0,5,0,7,0,0,0]

另外请注意，您不必对每个素数都这样做，一旦素数达到sqrt（限制），您就可以停止，因为您知道所有非素数都已设置为零。

例如，10的平方根（本例中的限制）是3.162，这意味着当我们达到5时，我们不需要做任何事情，我们在这一点上完成了。但为什么呢？我们使用每个素数将其倍数设置为零，因为这些倍数不是素数；但是，由于5大于10的平方根，因此5的任何倍数都必须是小于5的数字的倍数，因此已经设置为0。

假设我们最初的范围是从20。20的平方根小于5，所以我们不需要检查5，因为5: 5 * 2 = 10, 5 * 3 = 15, 5 * 2 * 2 = 20的所有倍数都是较小素数的倍数，我们已经将它们设置为0。

Answer 2

质点筛的正确数据结构是一个位集，由整数值索引。Python没有一个内置的，但是因为你的限制很小（只有200万），一个常规的整数列表应该适合内存，即使它浪费了30倍或更多（它将需要大约9 MB的等效位集C需要250 KB）。

要提高速度，最重要的一点是除非通过直接索引（因此没有删除/删除），否则永远不要访问数组。此外，将筛的外循环限制为sqrt（限制），并将循环前进到下一个素数，而不是下一个值。

因此，类似这样的操作应该非常快（在我的旧机器上，使用香草Python 2.7大约需要2秒钟）。

import math, sys

def prime_sieve(limit):
    # Mark everything prime to start
    primes = [1 for x in xrange(limit)]
    primes[0] = 0
    primes[1] = 0

    # Only need to sieve up to sqrt(limit)
    imax = int(math.sqrt(limit) + 1)

    i = 2
    while (i < imax):
        j = i + i
        while j < limit:
            primes[j] = 0
            j += i

        # Move i to next prime
        while True:
           i += 1
           if primes[i] == 1:
               break

    return primes

s = prime_sieve(2000000)
print(sum(i for i in xrange(len(s)) if s[i] == 1))

Answer 3

问题是：

primes.remove(i*j)

。remove（）在大型列表上调用时效率非常低，因为它首先必须遍历整个列表以确定值的存在位置（如果有），然后必须再次遍历列表的一部分，以将移除元素后的所有元素向下移动一个位置。

这里还有其他使用数据结构的方法（包括使用列表的其他方法和完全使用其他数据结构的方法）会更有效。

最后：您的代码在迭代的同时修改primes（primes中的i就是这样做的）。这通常被认为是一件坏事，因为在迭代时修改某些内容可能是未定义的行为。