本日看了《机器姬》，探讨人工智能话题的影戏，豆瓣评分7.5，照旧蛮不错的一部影戏。影片1:09:29处呈现了一段python代码，细看了一下，发明是筛法求质数的python代码，写得很是简洁的。先贴个影戏的截图：
影片里的代码略微有点恍惚，我从头打一遍，是下面这个样子的
#coding:utf8
import sys
def sieve(n):
#compute primes using sieve eratosthenes
x = [1] * n
x[1] = 0
for i in range(2,n/2):
j = 2 * i
while j < n:
x[j] = 0
j = j + i
return x
def prime(n,x):
#Find nth prime
i = 1
j = 1
while j <= n:
if x[i] == 1:
j = j + 1
i = i + 1
return i-1
x = sieve(10000)
code = [1206,301,384,5]
key = [1,1,2,2]
sys.stdout.write("".join(chr(i) for i in [73,83,66,78,32,61,22]))
for i in range(0,4):
sys.stdout.write(str(prime(code[i],x)-key[i]))
代码的最后打印出来下面这个很奇怪的对象，目测是一本书的ISBN，上豆瓣查了一下，是Embodiment and the Inner Life，是关于思维、意识的内容的，和本片的主题息息相关。
ISBN =9780199226559[Finished in 0.1s]
重点照旧前面的两个函数实现的筛法求质数。首先先容一下什么是筛法，筛法相传是古希腊的埃拉托斯特尼发现的一种检测素数的算法。筛法的思路很是简朴，可以用下面的动图来描写。给定一个范畴，首先用2去筛，把所有2的倍数都筛掉，然后再用3筛，用5筛，不绝反复下去……
再来看代码
def sieve(n): //对n以内的数举办筛选，返回一个长度为n的布尔数组 #compute primes using sieve eratosthenes x = [1] * n //界说长度为n的布尔数组（实际上影戏里用1和0来暗示true和false了） x[1] = 0 //1既不是素数也不是合数，设为0 for i in range(2,n/2)://i从2开始一直到n/2 j = 2 * i //j从2倍i开始 while j < n: x[j] = 0 //把所有i的倍数筛除 j = j + i //下一个i的倍数 return x //返回数组 def prime(n,x): //求第n个素数，只需要在筛选好的布尔数组中找第n个标志为1的数就可以了 #Find nth prime i = 1 //初始化为1 j = 1 while j <= n: //在布尔数组中寻找第n个标志为1的数 if x[i] == 1: j = j + 1 i = i + 1 return i-1 //前面轮回中i多加了一次，返回时需要减1
可以看到，利用筛法求第n个质数的时间巨大度为O(n)，缺点在需要提前求得筛选的功效，增加了空间巨大度，筛选功效可以用比特位来暗示以节减空间。
另外尚有一个问题，在求第n个质数的时候，如何要确定第n个质数的大抵范畴，以确定筛选功效的布尔数组长度。按照素数定理，可以用来估算某个范畴内的素数个数，可以用公式x/ln(x)来描写，ln暗示自然对数，假设要预计10000以内有几多质数，代入公式10000/ln(10000)获得的功效为1085.73,利用上面的筛法获得的10000觉得的质数个数为1229，可以看到预计值比实际值略小一点，预计的范畴越大，预计值与实际值的误差越小。实际利用中可以通过公式计较预计值，然后按必然百分比扩大范畴即可。
文章转自: http://segmentfault.com/a/1190000004162829
