資訊專欄INFORMATION COLUMN
摘要：影片處出現(xiàn)了一段代碼，細(xì)看了一下，發(fā)現(xiàn)是篩法求質(zhì)數(shù)的代碼，寫得非常簡練的。重點(diǎn)還是前面的兩個函數(shù)實(shí)現(xiàn)的篩法求質(zhì)數(shù)。
今天看了《機(jī)械姬》，探討人工智能話題的電影，豆瓣評分7.5，還是蠻不錯的一部電影。影片1:09:29處出現(xiàn)了一段python代碼，細(xì)看了一下，發(fā)現(xiàn)是篩法求質(zhì)數(shù)的python代碼，寫得非常簡練的。先貼個電影的截圖：
影片里的代碼略微有點(diǎn)模糊，我重新打一遍，是下面這個樣子的
#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，是關(guān)于思維、意識的內(nèi)容的，和本片的主題息息相關(guān)。
ISBN =9780199226559[Finished in 0.1s]
重點(diǎn)還是前面的兩個函數(shù)實(shí)現(xiàn)的篩法求質(zhì)數(shù)。首先介紹一下什么是篩法，篩法相傳是古希臘的埃拉托斯特尼發(fā)明的一種檢測素數(shù)的算法。篩法的思路非常簡單，可以用下面的動圖來描述。給定一個范圍，首先用2去篩，把所有2的倍數(shù)都篩掉，然后再用3篩，用5篩，不斷重復(fù)下去......
再來看代碼
def sieve(n): //對n以內(nèi)的數(shù)進(jìn)行篩選，返回一個長度為n的布爾數(shù)組
#compute primes using sieve eratosthenes
x = [1] * n //定義長度為n的布爾數(shù)組（實(shí)際上電影里用1和0來表示true和false了）
x[1] = 0 //1既不是素數(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 //下一個i的倍數(shù)
return x //返回數(shù)組
def prime(n,x): //求第n個素數(shù)，只需要在篩選好的布爾數(shù)組中找第n個標(biāo)記為1的數(shù)就可以了
#Find nth prime
i = 1 //初始化為1
j = 1
while j <= n: //在布爾數(shù)組中尋找第n個標(biāo)記為1的數(shù)
if x[i] == 1:
j = j + 1
i = i + 1
return i-1 //前面循環(huán)中i多加了一次，返回時需要減1
可以看到，使用篩法求第n個質(zhì)數(shù)的時間復(fù)雜度為O(nlog(n))，缺點(diǎn)在需要提前求得篩選的結(jié)果，增加了空間復(fù)雜度，篩選結(jié)果可以用比特位來表示以節(jié)省空間。
此外還有一個問題，在求第n個質(zhì)數(shù)的時候，如何要確定第n個質(zhì)數(shù)的大致范圍，以確定篩選結(jié)果的布爾數(shù)組長度。根據(jù)素數(shù)定理，可以用來估算某個范圍內(nèi)的素數(shù)個數(shù)，可以用公式x/ln(x)來描述，ln表示自然對數(shù)，假設(shè)要估計10000以內(nèi)有多少質(zhì)數(shù)，代入公式10000/ln(10000)得到的結(jié)果為1085.73,使用上面的篩法得到的10000以為的質(zhì)數(shù)個數(shù)為1229，可以看到估計值比實(shí)際值略小一點(diǎn)，估計的范圍越大，估計值與實(shí)際值的誤差越小。實(shí)際使用中可以通過公式計算估計值，然后按一定百分比擴(kuò)大范圍即可。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/37682.html
摘要：首先明確一下概念質(zhì)數(shù)又稱素數(shù)，有無限個。質(zhì)數(shù)定義為在大于的自然數(shù)中，除了和它本身以外不再有其他因數(shù)的數(shù)稱為質(zhì)數(shù)。以內(nèi)質(zhì)數(shù)表質(zhì)數(shù)的個數(shù)是無窮的。 首先聲明本人水平有限，僅僅做一下記錄，有錯的地方請指正，文章垃圾請包容??！ 在網(wǎng)上不小心瀏覽到一篇技術(shù)博客，叫做《求質(zhì)數(shù)算法的N種境界（N>10）》，寫得很好，有興趣的讀者自己去搜索。然后就想自己去試試這篇博客里寫得各種求質(zhì)數(shù)的方法。 不想搭...
摘要：錨點(diǎn)定位雷佳音編輯雷佳音，年月日出生于遼寧省鞍山市，中國內(nèi)地男演員，年畢業(yè)于上海戲劇學(xué)院表演系。年月借話劇個人獲得有話劇界奧斯卡之稱的第屆佐臨獎最具潛力新人獎。年月日，雷佳音現(xiàn)身電影超時空同居開機(jī)儀式舉行。 錨點(diǎn)定位雷佳音 編輯雷佳音，1983年8月29日出生于遼寧省鞍山市，中國內(nèi)地男演員，2006年畢業(yè)于上海戲劇學(xué)院表演系。2010年，因飾演電視劇《杜拉拉升職記》里的約翰常而...
摘要：在高度結(jié)構(gòu)化的數(shù)據(jù)挖掘以及通過分析來評估和改進(jìn)機(jī)器學(xué)習(xí)模型方面，是國際領(lǐng)先的研究人員。在機(jī)器學(xué)習(xí)里，我并沒有涉及強(qiáng)化學(xué)習(xí)的內(nèi)容。這些準(zhǔn)備讓讀者了解機(jī)器學(xué)習(xí)能做什么，然后我的書能幫助他們了解機(jī)器學(xué)習(xí)怎么工作。 非商業(yè)轉(zhuǎn)載請注明作譯者、出處，并保留本文的原始鏈接：http://www.ituring.com.cn/art... 訪談對象： Peter Flach，布里斯托大學(xué)人工智能教授，...
閱讀 3468·2021-09-08 09:36
閱讀 2564·2019-08-30 15:54
閱讀 2355·2019-08-30 15:54
閱讀 1771·2019-08-30 15:44
閱讀 2395·2019-08-26 14:04
閱讀 2446·2019-08-26 14:01
閱讀 2883·2019-08-26 13:58
閱讀 1337·2019-08-26 13:47
