寻找质数

前几天在twitter上第一次看到“质数币”，和比特币最大的不同是：比特币浪费CPU资源，而质数币用CPU找质数。

后来想，选个质数手机号。在网上没找到这样的质数集。反正质数的概念简单，就着手自己写一个吧。

第一版的算法很简单，从2开始往更大的数去寻找质数，像这样：2 3 4 5 6 7 8……。怎么确定这个数是质数呢？也是从小到大挨个儿取余，最大的数是本身-1，整个过程值都不是0的情况可以确定这是质数。

第一版运行很好，运行了16小时了，找到了809691个质数，最大质数是12353311。

这样的速度太慢，因为我要找到156xxxxxxxx这样的11位数字，照这样的速度也不知道跑到那一年才能找到，必须优化之。

第二版的优化首先确定两个方向：1，取余计算不必是2-n之间的所有整数，只需要之间的质数即可；2，不必是2-n之间的所有质数，只要是2-sqrt(n)之间的质数即可。

第二版代码是：

#/usr/bin/env python
import array,math

prime_arr=array.array('l',[])
for line in open('list','r'):
    prime_arr.append(int(line))

def is_prime(n):
    for ex in prime_arr:
        if math.sqrt(n)<ex: return True
        elif n%ex==0: return False
    return True

for i in xrange(prime_arr[-1]+1,15613980000):
    if is_prime(i):
        prime_arr.append(i)
        print i

这一下速度快了不少，运行了24小时了，共找到73620894个质数，最大的数为1476695161，程序还在运行着，看看多少天能找到11位的质数。

2014-03-30 更新:

程序跑了26天才把15613980000以内的质数找完，用GOLANG依照同样的逻辑试了一下让我很惊讶，GOLANG写的程序运行速度是python版的十倍以上。

为了更充分地说明速度的差距，就花了些精力把golang版完善了一下，第一次运行约19小时程序就被系统killed，第二次也是同样的情况，怀疑是内存的原因；还有就是跑出来的质数会存放在本地文件里，再一次运行就可以读文件后从上次运行结尾处接着找质数，可是GOLANG版的程序一跑就内存溢出。

我怀疑是a=append(a,i)的原因，但是又找不到替代方案。

python版慢golang版快，python版本开发简单运行顺利、golang版本开发复杂一些可运行时问题解决不了；python面向程序员的界面更简单，golang中的变量类型数是python的好几倍。

想到另外一个事，python可以用c来实现计算量密集的部分，那天大概看了一下貌似不复杂，如果有机会我想把launch平台统计模块的计算部分用C写一下。