什么是素数（你知道怎么样才能找到一个素数吗？）
素数
令人沉迷无法自拔
1一个关于素数的趣闻
2017年12月26日，数学界发生一件大事，美国一位普通的电气工程师Jonathan Pace，在他成为GIMPS计划志愿者的第14个年头，找到第50个梅森素数，即277232917-1，这是目前为止人类发现的最大素数，共计23249425位。
紧接着，2018年年初，又发生了一件与之相关的趣闻。
在第50个梅森素数诞生后的两周后，日本虹色社紧急发行了一本书，名叫《2017年最大的素数》（『2017年最大の素数』），厚约32mm，共719页，整本书只印了一个数，第50个梅森素数。
数学类书籍向来不是那么好卖，但是，这本书在发行两周后迅速攀上日本亚马逊数学类“畅销书第1位”，卖到断货，出版社被迫紧急加印应付市场。
如果你对一个两千多万位的数字没有概念的话，看到这本书的厚度你应该就知道了
出版社的山口和男先生在接受媒体采访时表示，印这样一本书其实并没有什么特别的目的。他还曾考虑将圆周率π印成书，但因为圆周率在小数点以后的位数是无限的，只好作罢。
但2017年年底梅森素数的诞生，再一次促动他把数字印成书的神经，促使他以最快的速度把这本书发行出版。这本书不仅实现了山口和男先生纯粹的愿望，而且这本书的销售过程一不小心成为了出版界的奇闻。
《2017年最大的素数》内页，里面密密麻麻都是数字
对于读者来说，把这本书买回家，精神意义远大于实际意义。自17世纪法国数学家马林·梅森（Marin Mersenne）开始，人们就开始不断寻找梅森素数。找到第50个梅森素数，是数学领域的重大发现，也是人类发展一个新的里程碑。把这个里程碑带回家，这本书更多的是一种信物，代表人类力求不断进步，勇攀高峰的精神。
2什么是素数？
为什么一个梅森素数的诞生，引起如此大的轰动？我们先来了解一下什么是素数（prime number）。
素数定义为大于1的自然数中，除了1和它本身以外不再有其他因数。
这个定义很容易理解，以小于10的自然数为例，2、3、5、7是素数，比如7只能被分解为1乘以7，没有其他分解方式。对于其他数来说，比如8可以被分解为2×4，所以8不能是素数。
素数如同数字的原子一样，是构造其他数字的基石。自然数是无限个，那么作为基石的素数到底有多少个呢？
这个问题在2300多年前得到了解答：素数有无穷多个。古希腊数学家欧几里得在《几何原本》中给出了简洁漂亮的证明。
虽然素数有无穷多个，但要发现和验证大素数却不容易，这就是素数的秘密。有多不容易呢？
我们可以很快地把50以内的素数列举出来：
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47……
它们看起来很密集，但随着素数越大，它们之间的距离渐渐变长。重要的是，它们的分布距离是不均等的。要找到一个大的素数，往往需要巨量的计算，要分解和验证它也是这样。为了掌握素数的规律，数学家绞尽脑汁。
其中，有两个关于素数的著名猜想：
这两个猜想在数学史上非常有名，千百年来许多数学家梦寐以求希望亲手攻克的难题。可喜的是，在最近的100年，这两个猜想得到了重大的突破。
其中，中国数学家张益唐在2012年成功地证明了存在无数对孪生素数，而且其中每一对中的两个素数之差，不超过7000万。虽然只有把7000万降到2才能最终证明孪生素数猜想，但他突破性地把孪生素数的距离，从无限变成了有限。
在张益唐取得这一突破之后，不少学者尝试用他的方法缩小间隔，进一步拉近了与最终解决孪生素数猜想的距离。在2014年2月， 7000万已被缩小至246。
另一方面，中国数学家陈景润在1966年成功证明了“1+2”的成立，距离哥德巴赫猜想“1+1”的成立仅一步之遥。
这里引入一个概念叫殆素数，殆素数是素因子个数不多的正整数。
假设N是偶数，虽然目前不能证明N是两个素数之和，但足以证明它能够写成两个殆素数的和，即N=A+B，其中A和B的素因子个数都不太多，譬如说素因子个数不超过10。
我们可以用“a+b”来表示如下命题：每个大偶数N都可表为A+B，其中A和B的素因子个数分别不超过a和b。显然，哥德巴赫猜想就可以写成"1+1"。
在这一方向上的进展都是用所谓的筛法得到的。自从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素数有什么用
为什么科学家们这么热衷于寻找素数？一方面，是对于自身理想的追求，孜孜不倦地在数学的高峰上攀登。但另一方面，素数在实际场景当中却体现很大的价值。
素数在计算机领域当中的应用，莫过于信息的加密，其中有著名的RSA算法（小智以前写过RSA算法的介绍，点击传送门）。由于目前大整数的因式分解，即寻找一个大整数的素数因子，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。也就是说，只要密钥长度足够长，寻找素数因子的时间则非常长，用RSA加密的信息实际上是不能被解破的。因此，素数在密码学当中有重要的地位。
只有拥有钥匙（私钥）的情况下，才能解出信息
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数可以设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强齿轮的耐用度，减少故障。
汽车序列式变速箱的细节图
北美的周期蝉（Magicicada）有着奇特的生命周期。它们要经过一段漫长的时间，每13或17年，才会成群地破土而出。
自17世纪中叶起，科学家就一直对周期蝉的生命周期困惑不已。它们遵循着相同的基本生命周期：幼虫在地底生活13或17年，然后在夏季大量出现。它们爬上树，蜕皮，成长为成虫，然后在短短数周内，成虫相遇、交配、产卵。孵化后，幼虫会回到地底，等待下一个轮回。
为什么是13或者17年，而不是其他数字，而恰好这个数字是素数？
当这些周期蝉大量出土繁殖时，周期蝉的天敌大吃特吃，天敌有更多的营养进行繁殖，天敌数量将会大大增加。假设天敌是6年才能性成熟，它的后代又要6年之后才会性成熟繁殖，因为没有周期蝉吃，它们的数量一直是回落的。再假设周期蝉的周期是18年，那么天敌们将在第18年继续大吃特吃，在这个18年周期内产生了更多的天敌，这样每过18年，天敌的总数不断上涨，周期蝉的数量就越来越少了。同理，周期是16年的周期蝉，很可能会被周期为2、4、8年的天敌吃到绝种。
而13年蝉和17年蝉刚好避过了这些可能性，因为13和17是素数，除非天敌每年繁殖，或者刚好13或17年繁殖，否则不可能成为帮助天敌进行繁殖。因为13年蝉和17年蝉选择了素数的生命周期，大幅度降低了帮助天敌繁殖的机会，使得自己能够生存到今天。
密密麻麻的趴在栅栏上的周期蝉
数学之美，无处不在。就以素数这个特性而言，一方面，人类在计算机的加密算法上，运用到了素数分布的特性；另一方面，大自然按照既定的规律自然运行，却也产生素数周期的特性，素数周期的生物产生了最大的适应性，实在令人惊叹。这让人联想到，诸如蕴含费波那契数列的松果，具有分形结构的山川河流（传送门），与其说这是自然界的神工鬼斧，倒不如说，这是数学规律幕后主使的结果。
松果顺时针8环，逆时针13环，这正是费波那契数列当中的数字