今天看了《機(jī)械姬》竿屹，探討人工智能話題的電影各淀，豆瓣評(píng)分7.5盾鳞，還是蠻不錯(cuò)的一部電影犬性。影片1:09:29處出現(xiàn)了一段python代碼，細(xì)看了一下腾仅，發(fā)現(xiàn)是篩法求質(zhì)數(shù)的python代碼乒裆，寫得非常簡(jiǎn)練的。先貼個(gè)電影的截圖：
影片里的代碼略微有點(diǎn)模糊推励，我重新打一遍鹤耍，是下面這個(gè)樣子的
#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]))
代碼的最后打印出來下面這個(gè)很奇怪的東西肉迫，目測(cè)是一本書的ISBN，上豆瓣查了一下稿黄，是Embodiment and the Inner Life喊衫，是關(guān)于思維、意識(shí)的內(nèi)容的杆怕，和本片的主題息息相關(guān)族购。
ISBN =9780199226559[Finished in 0.1s]
重點(diǎn)還是前面的兩個(gè)函數(shù)實(shí)現(xiàn)的篩法求質(zhì)數(shù)。首先介紹一下什么是篩法陵珍，篩法相傳是古希臘的埃拉托斯特尼發(fā)明的一種檢測(cè)素?cái)?shù)的算法寝杖。篩法的思路非常簡(jiǎn)單，可以用下面的動(dòng)圖來描述互纯。給定一個(gè)范圍瑟幕，首先用2去篩，把所有2的倍數(shù)都篩掉留潦，然后再用3篩只盹，用5篩，不斷重復(fù)下去......
再來看代碼
def sieve(n): //對(duì)n以內(nèi)的數(shù)進(jìn)行篩選愤兵，返回一個(gè)長(zhǎng)度為n的布爾數(shù)組
#compute primes using sieve eratosthenes
x = [1] * n //定義長(zhǎng)度為n的布爾數(shù)組（實(shí)際上電影里用1和0來表示true和false了）
x[1] = 0 //1既不是素?cái)?shù)也不是合數(shù)鹿霸，設(shè)為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的倍數(shù)篩除
j = j + i //下一個(gè)i的倍數(shù)
return x //返回?cái)?shù)組
def prime(n,x): //求第n個(gè)素?cái)?shù)，只需要在篩選好的布爾數(shù)組中找第n個(gè)標(biāo)記為1的數(shù)就可以了
#Find nth prime
i = 1 //初始化為1
j = 1
while j <= n: //在布爾數(shù)組中尋找第n個(gè)標(biāo)記為1的數(shù)
if x[i] == 1:
j = j + 1
i = i + 1
return i-1 //前面循環(huán)中i多加了一次秆乳，返回時(shí)需要減1
可以看到懦鼠，使用篩法求第n個(gè)質(zhì)數(shù)的時(shí)間復(fù)雜度為O(nlog(n))，缺點(diǎn)在需要提前求得篩選的結(jié)果屹堰，增加了空間復(fù)雜度肛冶，篩選結(jié)果可以用比特位來表示以節(jié)省空間。
此外還有一個(gè)問題扯键，在求第n個(gè)質(zhì)數(shù)的時(shí)候睦袖，如何要確定第n個(gè)質(zhì)數(shù)的大致范圍，以確定篩選結(jié)果的布爾數(shù)組長(zhǎng)度荣刑。根據(jù)素?cái)?shù)定理馅笙，可以用來估算某個(gè)范圍內(nèi)的素?cái)?shù)個(gè)數(shù)，可以用公式x/ln(x)來描述厉亏，ln表示自然對(duì)數(shù)董习，假設(shè)要估計(jì)10000以內(nèi)有多少質(zhì)數(shù)，代入公式10000/ln(10000)得到的結(jié)果為1085.73,使用上面的篩法得到的10000以為的質(zhì)數(shù)個(gè)數(shù)為1229爱只，可以看到估計(jì)值比實(shí)際值略小一點(diǎn)皿淋，估計(jì)的范圍越大，估計(jì)值與實(shí)際值的誤差越小。實(shí)際使用中可以通過公式計(jì)算估計(jì)值窝趣，然后按一定百分比擴(kuò)大范圍即可疯暑。
今年第六屆大會(huì)PyConChina2016，由PyChina.org發(fā)起哑舒，CPyUG/TopGeek 等社區(qū)協(xié)辦妇拯，將在2016年9月10日（上海）9月25日（深圳）10月15日（北京、杭州）地舉辦的針對(duì)Python開發(fā)者所舉辦的最盛大和權(quán)威的Python相關(guān)技術(shù)會(huì)議洗鸵，由PyChina社區(qū)主辦乖阵，致力于推動(dòng)各類Python相關(guān)的技術(shù)在互聯(lián)網(wǎng)、企業(yè)應(yīng)用等領(lǐng)域的研發(fā)和應(yīng)用预麸。
您可以點(diǎn)擊此處
了解更多詳情瞪浸，或者掃描下圖二維碼：
