電影里的代碼之《機械姬》：篩法求質數

simon_chen 發布于2019-07-24 18:19 / 1467人閱讀

摘要：影片處出現了一段代碼，細看了一下，發現是篩法求質數的代碼，寫得非常簡練的。重點還是前面的兩個函數實現的篩法求質數。

今天看了《機械姬》，探討人工智能話題的電影，豆瓣評分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(nlog(n))，缺點在需要提前求得篩選的結果，增加了空間復雜度，篩選結果可以用比特位來表示以節省空間。

此外還有一個問題，在求第n個質數的時候，如何要確定第n個質數的大致范圍，以確定篩選結果的布爾數組長度。根據素數定理，可以用來估算某個范圍內的素數個數，可以用公式x/ln(x)來描述，ln表示自然對數，假設要估計10000以內有多少質數，代入公式10000/ln(10000)得到的結果為1085.73,使用上面的篩法得到的10000以為的質數個數為1229，可以看到估計值比實際值略小一點，估計的范圍越大，估計值與實際值的誤差越小。實際使用中可以通過公式計算估計值，然后按一定百分比擴大范圍即可。

GPU云服務器云服務器電影里的代碼 python 求質數 java編寫求質數 js用函數求質數

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37682.html

求質數的各個算法比較

摘要：首先明確一下概念質數又稱素數，有無限個。質數定義為在大于的自然數中，除了和它本身以外不再有其他因數的數稱為質數。以內質數表質數的個數是無窮的。首先聲明本人水平有限，僅僅做一下記錄，有錯的地方請指正，文章垃圾請包容！！在網上不小心瀏覽到一篇技術博客，叫做《求質數算法的N種境界（N>10）》，寫得很好，有興趣的讀者自己去搜索。然后就想自己去試試這篇博客里寫得各種求質數的方法。不想搭...

QLQ 2019-06-27 16:17 評論0 收藏0
錨點定位

摘要：錨點定位雷佳音編輯雷佳音，年月日出生于遼寧省鞍山市，中國內地男演員，年畢業于上海戲劇學院表演系。年月借話劇個人獲得有話劇界奧斯卡之稱的第屆佐臨獎最具潛力新人獎。年月日，雷佳音現身電影超時空同居開機儀式舉行。錨點定位雷佳音編輯雷佳音，1983年8月29日出生于遼寧省鞍山市，中國內地男演員，2006年畢業于上海戲劇學院表演系。2010年，因飾演電視劇《杜拉拉升職記》里的約翰常而...

ivydom 2019-04-23 11:55 評論0 收藏0
《機器學習》作者Peter Flach：好萊塢也借AI上頭條

摘要：在高度結構化的數據挖掘以及通過分析來評估和改進機器學習模型方面，是國際領先的研究人員。在機器學習里，我并沒有涉及強化學習的內容。這些準備讓讀者了解機器學習能做什么，然后我的書能幫助他們了解機器學習怎么工作。非商業轉載請注明作譯者、出處，并保留本文的原始鏈接：http://www.ituring.com.cn/art... 訪談對象： Peter Flach，布里斯托大學人工智能教授，...

MartinHan 2019-07-25 10:47 評論0 收藏0