电影里的代码之《机械姬》：筛法求质数

simon_chen 发布于2019-07-24 18:19 / 1270人阅读

摘要：影片处出现了一段代码，细看了一下，发现是筛法求质数的代码，写得非常简练的。重点还是前面的两个函数实现的筛法求质数。

今天看了《机械姬》，探讨人工智能话题的电影，豆瓣评分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，可以看到估计值比实际值略小一点，估计的范围越大，估计值与实际值的误差越小。实际使用中可以通过公式计算估计值，然后按一定百分比扩大范围即可。

云服务器混合云电影里的代码 python 求质数 java编写求质数 js用函数求质数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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