如何用 python 计算十亿内的素数总和？

今天想加个QQ群，得回答这个问题才能通过请求。
我本来想想很简单啊用下面这个式子就能算了。
reduce(lambda x,y:x+y,[x for x in range(1,N+1,2) if len([y for y in range(1,x+1,2) if x%y==0])==2],2)
结果到后来抛出个错误说MemoryError。
研究了好会儿还是没什么好法子，各位有什么看法？

素数

range

式子

21 replies • 2015-04-19 00:03:00 +08:00

ppdg

Apr 18, 2015 via Android

最快的应该是筛法吧

msg7086

Apr 18, 2015

筛法用C++大概1分钟内能出结果。你这个式子建议你先算算要多少内存和运算量吧……

ybbswc

Apr 18, 2015

这个range太大了。所以抛出error吧。
http://www.zhihu.com/question/29580448
知乎上有这个提问，不过好多都是C的。

illuz

Apr 18, 2015

Python 的话，去数学网站上爬呀，比如：
http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php
http://www.bigprimes.net/archive/prime/
第二个会好爬点，不过也要爬个 6w 页的说。
网上爬总比爆内存好...

futursolo

Apr 18, 2015

使用生成器可以避免上面所说的内存不够用的情况。

这里给一个例子：（V2EX会把代码中的空格自动删掉，请自己补全）

import math
import time

def is_prime(number):
if number > 1:
if number == 2:
return True
if number % 2 == 0:
return False
for current in range(3, int(math.sqrt(number) + 1), 2):
if number % current == 0:
return False
return True
return False

def get_primes(number):
while True:
if is_prime(number):
yield number
number += 1

start = time.time()

prime = get_primes(1)
prime_sum = 0
while True:
this_prime = next(prime)
if this_prime <= 1000000:#改一下这里的数字
prime_sum += this_prime
else:
break
print("Result:" + str(prime_sum))
print ("Finished! Time Used: " + str(time.time() - start) + "s.")

至于楼上所说的筛法算素数的问题，可能也需要比较大的内存
（你还是要把已经算出来的素数保存起来，在这里暂时不用了）

这个是Python3的代码，Python2请自己改一下。

要想算的快一点，可以使用PyPy3。

sinux

Apr 18, 2015

写了一个比较朴素的，内存倒是没爆...

def print_prime(n):
____q = 0
____for i in xrange(0, n):
________found = True
________for j in xrange(2, i):
________if i % j == 0:
____________found = False
____________break
________if found:
____________q += i
____print q

if __name__ == '__main__':
____print_prime(1000000000)

sinux

Apr 18, 2015

这缩进不忍直视