0

欧拉计划问题 10：

10以下的素数之和为2 + 3 + 5 + 7 = 17。

求两百万以下的所有素数之和。

我认为我的代码中没有任何错误。但是要给出答案确实需要很多时间。我尝试过使用 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()
4

5 回答 5

4

问题是这样的：

primes.remove(i*j)

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

这里还有其他方法可以使用数据结构（使用列表的其他方法，以及完全使用其他数据结构的其他方法）会更有效。

最后：您的代码primes在您迭代它的同时进行修改（这就是for i in primes正在做的事情）。这通常被认为是一件坏事，因为在迭代时修改某些东西可能是未定义的行为。

于 2013-08-04T20:49:19.113 回答
1

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

你从列表开始：

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

您想将每个不是素数的元素设置为 0，并保留素数。

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

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

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

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

[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(limit) 您可以停止，因为您知道所有非素数都已设置为零。

例如，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。

于 2013-08-04T21:21:44.907 回答
1

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

速度的重要一点是永远不要访问数组，除非通过立即直接索引（所以没有删除/删除）。此外，将筛子的外循环限制为 sqrt(limit)，并将循环推进到下一个素数，而不是下一个值。

所以这样的事情应该很快（在我的旧机器上使用 vanilla 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))
于 2013-08-05T01:55:53.730 回答
1

这是埃拉托色尼筛的一个简单版本，适用于计算总和，而不是形成小于n的素数列表：

def sumPrimes(n):
    sum, sieve = 0, [True] * n
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

有更好的方法来执行筛分，但是上面显示的函数对于这个 Project Euler 问题已经足够了；它应该在大约一秒钟内返回总和。如果你对使用素数编程感兴趣，我谦虚地在我的博客上推荐这篇文章。

于 2013-10-01T23:21:07.143 回答
0 
    def isPrime(n):
        if n < 2: return "Neither prime, nor composite"
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return False
        return True



 def sumPrime():
        sumT = 0
        for i in range(2,2000000):
            if(isPrime(i)):
                sumT = sumT + i
        return sumT
于 2018-10-17T16:41:13.467 回答