什么叫素数|你知道怎么样才能找到一个素数吗？( 二 )

在这一方向上的进展都是用所谓的筛法得到的。自从1920年挪威数学家布朗（Brun）证明了“9+9”以来，这个公式在各大数学家手上不断进行简化，在1966年由我国数学家陈景润证明了“1+2” 。
3素数寻找计划——GIMPS
素数当中，有一类素数非常特别，形如2p-1，17世纪法国数学家马林梅森对它进行了深入研究。为了纪念梅森的贡献，学界把这种数称之为梅森数，如果梅森数为素数，则称之为梅森素数。
在只能手工计算的时代，人们就开始了对梅森素数的寻找，直到19世纪末，人们只找到了12个梅森素数。p值分别是：2，3，5，7，13，17，百思特网19，31，61，89，107，127 。
在计算机诞生以后，人们搜索梅森素数的速度加快，直到1996年为止，数学家使用了超级计算机Cray-T94，发现了第34个梅森素数。
进入互联网时代，一个更加精妙的方法诞生了。1996年1月，美国数学家及程序设计师乔治沃特曼（George Woltman）编写了一个梅森素数计算程序。他把程序放在网页上供数学家和数学爱好者免费使用，这就是最初的互联网梅森素数大搜索计划了（Great Internet Mersenne Prime Search，GIMPS）。任何拥有个人电脑的人都可以加入GIMPS，成为一名素数猎人。从1997年至今，所有新的梅森素数都是通过GIMPS分布式计算项目发现的。这个项目成功聚集了数十万台计算机进行一个问题的计算，它的计算能力已经远远超出我们的想象。
其中，最新第50个梅森素数的发现，就是美国一位普通的电气工程师Jonathan Pace，用一台普通的家庭计算机，CPU型号是i5-6600，幸运地通过GIMPS发现了这个梅森素数，不仅在数学史上留下了自己的名字，而且得到了3000美元的奖励。（大家如果有兴趣，可以下载一个试试，第一个找到超过1亿位数梅森素数的人，奖励15万美元）

4素数寻找算法
素数行踪不定，分布未知，怎么样才能找到素数?
在公元前2世纪希腊数学家埃拉托斯特尼（Eratosthenes），就已经提出了一个非常简单而且有效的素数筛法，我们称之为埃拉托斯特尼筛法（Sieve of Eratosthenes）。核心是：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
具体的筛法如下：

第1步：确定需要筛选素数的范围，确定范围的最大值，比如是120 。
第2步：根号120的结果为10.95，所以只需要利用11以内所有素数的倍数来剔除120以内的数字，剩下的就是素数。首先剔除以2为倍数的数字，11以内剔除掉4，6，8，10这几个数字，同时剔除掉120以内所有以2为倍数的数字。
第3步：最小的未被剔除的数字为3，剔除以3为倍数的数字，11以内剔除9这个数字，同时剔除掉120以内所有以3为倍数的数字。
第4步：最小的未被剔除的数字为5，剔除以5为倍数的数字，11以内不需要剔除数字，同时剔除掉120以内所有以5为倍数的数字。
……
如此类推，可以将120以内的所有素数完全找到。

一个埃拉托斯特尼筛法的例子
5素数有什么用
为什么科学家们这么热衷于寻找素数？一方面，是对于自身理想的追求，孜孜不倦地在数学的高峰上攀登。但另一方面，素数在实际场景当中却体现很大的价值。
1、计算机领域
素数在计算机领域当中的应用，莫过于信息的加密，其中有著名的RSA算法（小智以前写过RSA算法的介绍，点击传送门）。由于目前大整数的因式分解，即寻找一个大整数的素数因子，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。也就是说，只要密钥长度足够长，寻找素数因子的时间则非常长，用RSA加密的信息实际上是不能被解破的。因此，素数在密码学当中有重要的地位。

只有拥有钥匙（私钥）的情况下，才能解出信息
2、工业领域
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数可以设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强齿轮的耐用度，减少故障。

汽车序列式变速箱的细节图
3、生物领域
北美的周期蝉（Magicicada）有着奇特的生命周期。它们要经过一段漫长的时间，每13或17年，才会成群地破土而出。