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

[napretep]

今天想加个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。
研究了好会儿还是没什么好法子，各位有什么看法？

[ppdg]

最快的应该是筛法吧

[msg7086]

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

[ybbswc]

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

[illuz]

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

[futursolo]

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

这里给一个例子：（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]

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

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]

这缩进不忍直视

[em70]

除了2以外，素数不可能是偶数，能降低一半的计算量

[sandideas]

用c语言计算，然后用python输出

[broono]

首先两位数以上以0，2，4，5，6，8结尾的数字，然后撒欢吧=-=先排除掉，能不算的就不算，内存就节省出来了。

[wy315700]

@sandideas
@em70
@sinux

果然说程序员算法差不是吹的，，，

http://blog.csdn.net/dinosoft/article/details/5829550

看看快速线性筛法吧。。。

[bcxx]

筛法保平安……

[tigerstudent]

之前为了提高博客访问量写了一篇博文描述了秒解的算法，一千多点击量。后来觉得实在没意思就删了。

[Kirscheis]

python用素数筛的话十亿以内只需要7G左右内存而已。

[Septembers]

@futursolo @sinux
代码可以发gist

[imn1]

http://bbs.csdn.net/topics/390350992

[XadillaX]

素数筛法。

[gladuo]

@wy315700 朴素筛法也就十来秒钟吧
个数 素数
的组合打印也就900M吧
建议算出来用py加就好。。。

[wy315700]

@gladuo 楼上好多N^2的算法。。。

[ant_sz]

如果用 BitSet 来做筛法的话空间会减少很多，可惜 Python 标准库里好像没有 BitSet 的实现。

[monkeymonkey]

只要求和的话，把素数表存成文件扫一遍不就算出和了么，也不需要多少内存。