2019-03-24

今天写下来，关于筛子算法，计算素数，针对大数的判断。
简单写一下算法，假设计算40000以内的素数。

筛子算法， 百度。
判断一个数x，是不是素数，只需判断这个数，能否整除 从3到 （根号下x 后 向上取整）之间的素数。
对于大数，这节省很多。
它的底层数学逻辑是，中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。

我的算法实现，伪码如下：
1、先建立一个4万个元素的list ，a =[0,1,0,1.......] ，这里的0 是因为下标从零开始，把所有的偶数下标，和偶数值，都写为0.
对这个list 进行处理，最后算法结束后，如果value=1 ，就记录其下标，这些下标组成素数列表。
2、从网上获得，素数列表，根据开方原理，c列表就是下面这些，只需要从3，到201 （201不是素数，删除）。
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 。
这很容易获得，百度。这里是处理边界的关键，
199X199=39601 201X199 =39999 ，而一眼就能看出39999 能被3整除。
又因为200,201，都不是素数。

3、开始循环，从b中取出第一个素数3， 把a[3k]设置为0，when 3k >40000 就停。
4、再从b中取出第二个素数5， 把a[5k]设置为0，when 5k >40000 就停。
5、继续循环，直到199，算法结束。
6、用下标，输出。
具体用python实现，代码如下，里面，用了，两种方法对比，还有计时，略复杂。
2.7 python 版本。

# -*- coding: UTF-8 -*-

import time,math
start=time.clock()

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
    
a8=list()    
for i3 in range(3,39998) :
    if is_prime(i3):
        a8.append(i3)       
#print(a8)
    
a=list()
a2=list()
'''
for i in range(0,39999):
    if i%2==0:
        a.append(0);
    else:
        a.append(1);
'''
#use another way to full the list a
listbase =[0,1,0,1]
a=listbase*10000
a.pop()
# check that the list a is the same 
#print(a)

c=[3 ,5 ,7, 11, 13, 17, 19, 23, 29,\
31 ,37, 41, 43 ,47 ,53 ,59 ,61, 67, 71,\
73, 79 ,83 ,89, 97,101 ,103 ,107 ,109 ,113,\
127,131, 137 ,139 ,149 ,151, 157, 163 ,167, 173,\
179 ,181, 191, 193 ,197 ,199]
#print(c)

#b=[3 ,5 ,7, 11, 13, 17, 19, 23, 29]
'''
for ka in c:
    ii=2
    while(ka*ii<=39998):
        #error control
        a[ka*ii]=0
        ii+=1
'''
sum=0
#这个地方是列表遍历，可以采用list.pop(),
#而后多线程跑函数mark。终于可以并行处理了。

for ka in c:
    #以下可以构造一个函数，比如，mark函数。    
    ii=ka            #开始点，很重要，直接把下面的if else 去掉了。
    #这个地方注意，列表下标溢出，应该加上错误处理
    while(ka*ii<=39998):
        #error control
        #if ii<ka:
           # ii+=1
           # continue
        #else:
        a[ka*ii]=0  #实现算法第三步
        sum+=1  #只是为了技术，看算法细节用
        ii+=2 # 去掉偶数     ，这是关键细节 
#print(a)

print(sum)  #only for test 


'''
结果
26890   #循环体执行的次数
0
0.146193

26890
0
0.126677     #a 的生成方式的不同，节约了时间。

通过与下面的算法比较，我的循环次数明显要小，几乎是一半，运行时间短
'''
'''
参考了 http://www.cnblogs.com/zqxLonely/p/4054550.html 的代码，感谢了。
for ka in c:
    #素数判断
    #if(flag[i]=='0'){
    j=ka*ka
    while(j<39999):
        a[j]=0
        sum+=1
        j+=ka
        
    #for (j=ka*ka;j<39999;j+=ka):
    #flag[j]='1';
        #a[j]=0
        #sum+=1
        #j+=ka
        
print(sum)
'''
'''
结果
53755   #循环体执行的次数
0
0.157856
'''
#for index,item in enumerate(sequence):
# get one list ,xiabiao and his value,a is a list,sushu
for index,item in enumerate(a):
#for i in a:
    if item==1:
        a2.append(index)
#print(a2[1:])

a9=a2[1:]
#duibi ,check it is good way to get the prime list 
print(cmp(a8,a9))

t=(time.clock()-start)
print (t)

但愿有用。注意，程序中的几个常数，应该在 前头定义，来增强程序的重用性。
编程坚持的底线是能用的常数，直接用。不要用变量。

这里指的是list c 的直接引入。

另外，从结构化考虑，写个函数，
应该读入40000后，根据根号40000 +1 ，去一个长长的素数list 中去截取，来生成list c 。