上学期上网络安全课的时候，杨老简单介绍了一些关于求素数的方法，闲着无聊，把筛选法用python实现了一下，发现有些好玩儿的地方：

原理：

　　素数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。在加密应用中起重要的位置，比如广为人知的RSA算法中，就是基于大整数的因式分解难题，寻找两个超大的素数然后相乘作为密钥的。一个比较常见的求素数的办法是) ，说简单一点就是画表格，然后删表格，如图所示：

　　从2开始依次往后面数，如果当前数字一个素数，那么就将所有其倍数的数从表中删除或者标记，然后最终得到所有的素数。

 

实现：

　　下面是python的一个实现：

　　实现1：

　　　　首先用dic存储n范围内的元素，然后依次标记，最后从头扫描一次dic，把合适的元素放在list中返回结果

1 def prime(n): 2     lis = {} 3     for i in xrange(2,n+1):      4         if not i in lis: 5             lis[i] = 1 6             k = i*2 7             while k <= n: 8                 lis[k] = 0 9                 k = k+i10     ans = []    11     for i in lis:12         if lis[i] == 1:13             ans.append(i)14     return ans

　　　　测试以后得到的结果是：求一千万以内的素数用了9.68秒

　　　　可是我觉得使用1个dict和1个list存会很浪费空间（其实不然，一千万以内的素数只有66万个，相对一千万来说可以忽略不计），所以想改进一下算法

　　实现2：

　　　　这次只用一个list存数字，然后遍历删除

1 def primeC(n): 2     lis = range(2,n+1) 3     for i in xrange(2,n+1): 4         if i in lis: 5             k = i+i 6             while k<=n: 7                 if k in lis: 8                     lis.remove(k) 9                 k = k+i10     return lis

　　　　因为无法在for中删除list，所以使用一个xrange，然后每次判断k是否在lis中再做删除，结果：求十万以内的素数一共花了186.79秒。

　　比较：

　　　　在时间上，第一个方法远远比第二个办法有效率，dict是哈希实现，查询的速度是常数级的，所以在标记合数的时候所花费的时间非常少，但是list是顺序表，不知道内部是怎么实现in 和 remove的，从时间上可以大概推测出应该是顺序查找实现的，所以用如下代码做了测试：

　

1 import random 2 import time 3 def find(source,test): 4     for each in test: 5         each in source 6  7 def remove(liss,test): 8     for each in test: 9         if each in liss:10             liss.remove(each)11 12 13 def removeDic(dicc,test):14     for each in test:15         if each in dicc:16             dicc[each] = 117 18 n = 10000019 m = 100020 liss = range(n)21 dicc = {i:0 for i in xrange(n)}22 test = []23 for i in xrange(m):24     test.append(random.randint(0,n))25     26 27 28 s = time.clock()29 find(liss,test)30 print time.clock()-s31 32 33 s = time.clock()34 find(dicc,test)35 print time.clock()-s36 37 s = time.clock()38 remove(liss,test)39 print time.clock()-s40 41 s = time.clock()42 removeDic(dicc,test)43 print time.clock()-s

　　　　结果是：　　

1.105269602810.000364793838322.117143183960.000374692766596

　　　　可以看出，在查找方面list是远远不如dict的，说明list不应该是哈希查找，而remove的时间也远远大于哈希的赋值时间（好像这是句废话- -）

　　　　不过由此判断第二种方法是一无是处的话未免言之过早了。因为第二种方法里面的实现是先申请了一段空间，然后再运算，而实现一的空间是动态增长的(在给哈希表赋值的那边体现)，所以如果涨到一半发现内存不够用的话就会报错（测试1亿数据的时候就出现了这个问题），而实现二一开始就会报错，而不用做前面的一系列无用功。

　　　　总之就是空间换时间，时间换空间的那些戏码。不过挺有意思。

小结：

　　求素数，list和dict的效率比较

　　最后小tip：好像python的垃圾回收机制有点什么问题，我结束一次测试以后以前的内存不回收，有空了解一下，有一个暂时解决的办法。可以调用gc  module里面的collect函数，挺好用~