Project Euler问题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()
问题是:
primes.remove(i*j)
在大列表上调用.remove()
时效率非常低,因为它首先必须遍历整个列表,以确定值存在的位置(如果有的话),然后必须再次遍历列表的一部分,以将删除的元素之后的所有元素下移一个位置。
这里还有其他更有效的方法可以使用数据结构(包括使用列表的其他方法和完全使用其他数据结构)。
最后:您的代码在对primes
进行迭代的同时修改它(这就是for i in primes
正在做的)。这通常被认为是一件坏事,因为在迭代过程中修改某个东西可能是未定义的行为。
素数筛的正确数据结构是一个由整数值索引的位集。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))
一个更有效的想法是这样的:
您从列表开始:
[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。20的平方根小于5,所以我们不需要检查5,因为5的所有倍数:5*2=10,5*3=15,5*2*2=20都是较小素数的倍数,我们已经将它们设置为0。
这里有一个简单版本的埃拉托斯特尼筛,适用于计算和,而不是形成小于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问题来说已经足够了;它应该在大约一秒钟内返回总数。如果你对素数编程感兴趣,我会在博客上推荐这篇文章。
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