看到个非常有趣算法,取出一串连续数字中所有的质数,大致原理如下:
2 3 4 5 6 7 8 9。。。。。。
首先从2开始,将所有2的倍数归零,也就是非质数,
2 3 5 7 9。。。。。。
接着将3的倍数清零
2 3 5 7。。。。。。
这串数字中的6既是2的倍数又是3的倍数,所以在归零3的倍数的时候,6的位置重复访问了一遍,虽然这时候6已经被清零了,由于这串数字是按照顺序排列的所以当归零3的倍数的时候可以直接从3*3=9开始归零,因为比3小的倍数在之前已经被归零了。

import math
def builder(num):
    num+=1
    a=[0]*num
    for i in range(2,num):
        a[i]=i
    return a    
if __name__=='__main__':
    num=500
    a=builder(num)#生成2到500的连续数字
    print a
    b=int(math.sqrt(num))#当遍历到最大数的二分之一次方时候,所有非质数已被清零
    for i in range(2,b):
        if a[i]!=0:
            j=i*i
            while j<=num:
                a[j]=0
                j=j+i
    i=0
    L=[]
    for n in a:#提取所有的非零数,即质数
        if n!=0:
            L.append(n)
    print L

经过测试在求2到1000000中所有的质数的时候仅仅花了0.5秒。