[分享]一个几十秒内就可以生成一百五十万个素数的程序

elimqiu

[这个贴子最后由elimqiu在 2010/09/29 01:30am 第 2 次编辑] 这个程序是用 python 写的。在大约 17 秒内结束计算并将结果存入文件（14Mb）。 计算结果是列出前 一百五十万个素数： 2，3，... 这个程序还可以继续算更多的素数。我把结果输入到了MySQL数据库. 利用数据库语言SQL 来找出一个正整数的素数分解。非常方便。 程序如下：

2. def saveprimes(n,start=0):
3. if n==2: return [2]
4. elif n<2: return []
5. s=range(3,n+1,2)
6. mroot = n ** 0.5
7. half=(n+1)/2-1
8. i=0
9. m=3
10. while m <= mroot:
11. if s[i]:
12. j=(m*m-3)/2
13. s[j]=0
14. while j<half:
15. s[j]=0
16. j+=m
17. i=i+1
18. m=2*i+3
19. result = [2]+[x for x in s if x]
20. if start > 0:
21. result = result[start:]
22. print "Count = ",len(result)
23. result = str(result)
24. FILE = open("primeL.txt","w")
25. FILE.writelines(result)
26. FILE.close()
27. print "Done!"

复制代码

============================================== 我的计算机不算很快： 2.2Gh 双核, 2Gb Ram 而已。 我的 python 2.7 (免费) 可以处理至少大到 9223372036854775807 （好像还可以大）的正整数。 [br][br]-=-=-=-=- 以下内容由 elimqiu 在 时添加 -=-=-=-=- python 程序的缩进很重要。如果上面的代码因为在拷贝时有出入，可向我要代码文件。

技术员

如果把它译成C,快不快?

elimqiu

下面引用由技术员在 2010/09/29 06:37pm 发表的内容：
如果把它译成C,快不快?

其实 python 的底层用的是 C 引擎。但是 C 本身的数据结构很费空间， 这短短的代码译成 C 是会慢些。不过我不是 C 的高手， 只是自己的估计。
代码的思想很简单，就是用筛法。先声明一个很长很长的 array (数串) 首项是2，其余都是奇数。接着的算法就是把是某数的倍数的项重置为0，然后输出非0的项。

技术员

可惜我不懂python,不然我会用C试一试.

elimqiu

下链接可以下到我由此得到的素数列文本：
http://ishare.iask.sina.com.cn/f/10386095.html

技术员

好可怕的文件,只能用word打开,太大了.

elimqiu

如果你用windows, 建议装一个UltraEditor 或者 NotePad++. 后者是免费的。 这种文本到那里面可以被很好地处理。

wangyangkee

elimqiu不是笨蛋，不愚蠢，不驴打滚，不狗屎堆逻辑，elimqiu不是白痴，elimqiu不是饭桶

wangyangkee

elimqiu不是笨蛋，不愚蠢，不驴打滚，不狗屎堆逻辑，elimqiu不是白痴，elimqiu不是饭桶，，，不是网痞，，，

elimqiu

前 一百五十万个素数 惹动了网痞的警觉。 于是先犬叫几声再说。 犬类也分档次的。一般抵挡的叫得响亮些。