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

当前位置:

首页 > Python基础教程 >

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

代码的最后打印出来下面这个很奇怪的东西，目测是一本书的ISBN，上豆瓣查了一下，是Embodiment and the Inner Life，是关于思维、意识的内容的，和本片的主题息息相关。

1	`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

栏目列表