什么是质数(你知道怎么求质数吗？)

素数

会上瘾的。

关于质数的轶事

2017年12月26日，数学界发生了一件大事。美国普通电气工程师乔纳森·佩斯(Jonathan Pace)在成为GIMPS志愿者的第14年发现了第50个梅森素数，即277232917-1。这是人类迄今为止发现的最大的素数，共有23249425个。

然后，2018年初，又发生了一个有趣的故事。

第50个梅森素数诞生两周后，日本弘色社紧急发行了一本名为《2017年最大素数》(简称《2017年最大素数》)的书，厚约32mm，共719页。整本书只印了一个数字，第50个梅森素数。

数学书从来没有这么好卖过。然而，这本书出版两周后，迅速攀升至日本亚马逊数学畅销书第一名。卖断货的时候，出版社被迫紧急加印，以应对市场。

如果你对一个超过2000万位数的数字没有概念，你应该知道这本书的厚度。

出版社的山口先生和一夫先生在接受媒体采访时表示，印刷这样一本书并没有什么特殊的目的。他也考虑过把圆周率印成书，但是因为圆周率小数点后的位数是无限的，所以不得不放弃。

然而，2017年底《梅森素数》的诞生，再次刺激了他将数字印刷成书的神经，促使他以最快的速度出版这本书。这本书不仅实现了山口那津男先生的纯粹愿望，而且这本书的销售过程一不小心还成了出版界的奇闻。

“2017年最大质数”内页全是数字。

对于读者来说，把这本书买回家的精神意义远大于现实意义。自17世纪法国数学家马林·梅森以来，人们一直在寻找梅森素数。找到第50个梅森素数是数学领域的重要发现，是人类发展的新里程碑。把这个里程碑带回家，这本书更多的是一个信物，代表了人类自强不息，勇攀高峰的精神。

什么是质数？

为什么一个梅森素数的诞生会引起如此大的轰动？我们先来了解一下什么是质数。

在定义为大于1的质数的自然数中，除了1和它本身，没有其他因素。

这个定义很好理解。以小于10的自然数为例。二、三、五和七是质数。比如7只能分解成1乘以7，没有其他的分解方式。对于其他的数，比如8可以分解成24，所以8不可能是质数。

就像质数的原子一样，它们是其他数的基石。自然数是无穷的，那么有多少个质数是基石呢？

这个问题在2300多年前就有了答案:素数有无穷多个。古希腊数学家欧几里得在《几何原本》中给出了简洁优美的证明。

质数虽然无穷多，但发现和验证大质数并不容易，这就是质数的秘密。难度有多大？

我们可以快速列出50以内的质数:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47……

它们看起来很密集，但是它们之间的距离随着质数的增大而变长。重要的是，它们的分布距离是不平等的。要找到一个大素数，往往需要巨大的计算量，分解验证也是如此。数学家绞尽脑汁想掌握质数定律。

其中，有两个关于素数的著名猜想:

孪生素数猜想:差为2的素数有无限对。

哥德巴赫猜想:所有偶数都可以表示为两个素数之和。

这两个猜想在数学史上非常有名。几千年来，许多数学家都梦想用自己的双手解决问题。幸运的是，在最近的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年挪威数学家布伦证明“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月，美国数学家和程序员乔治·沃特曼编写了一个梅森素数计算程序。他把程序放在网页上，供数学家和数学爱好者免费使用，这就是最初伟大的互联网梅森素数搜索(GIMPS)。任何拥有个人电脑的人都可以加入GIMPS，成为一名质数猎人。自1997年以来，所有新的梅森素数都是通过GIMPS分布式计算项目发现的。这个项目成功聚集了几十万台计算机来计算一个问题，其计算能力已经远远超出了我们的想象。

其中，最新的第50个梅森素数发现是美国普通电气工程师乔纳森·佩斯(Jonathan Pace)使用了一台CPU型号为i5-6600的普通家用电脑。幸运的是，他通过GIMPS发现了这个梅森素数，不仅在数学史上留下了自己的名字，还获得了3000美元的奖励。(有兴趣可以下载一个试试。第一个找到超过1亿位数的梅森素数的人将获得15万美元的奖励。)

4素数搜索算法

素数的去向是不确定的，分布也是未知的。怎样才能找到质数？

公元前2世纪，希腊数学家厄拉多塞提出了一种非常简单有效的素数筛选方法，我们称之为厄拉多塞筛。核心:要得到自然数N内的所有素数，必须消去所有不大于根号N的素数的倍数，剩下的都是素数。

具体筛选方法如下:

第一步:确定要过滤的素数的范围，确定范围的最大值，比如120。

第二步:根号120的结果是10.95，所以只需要11以内所有素数的倍数就可以消去120以内的数，剩下的都是素数。先去掉11以内的2、4、6、8和10的倍数的数字，去掉120以内的所有2的倍数的数字。

第三步:没有消掉的最小的数是3，排除3的倍数的数，排除11以内的数9，排除120以内的所有3的倍数的数。

第四步:没有消掉的最小的数是5，5的倍数的数都消掉。11以内的数字不需要消去，120以内的5的倍数的数字都消去。

……

以此类推，120以内的质数都可以完全找到。

埃拉托斯坦尼筛选方法的一个例子

五个质数有什么用？

为什么科学家如此热衷于寻找质数？一方面是对自己理想的追求，孜孜不倦地攀登数学高峰。另一方面，素数在实际场景中有很大的价值。

1.计算机字段

素数计算机领域的应用是信息的加密，其中有著名的RSA算法(小智之前写过RSA算法的介绍，点击入口)。目前用因式分解求大整数的质因数是非常困难的。目前除了暴力破解，没有找到其他有效的方法。也就是说，只要密钥长度足够长，求质因数的时间就很长，RSA加密的信息实际上是无法解密的。因此，素数在密码学中起着重要的作用。

只有你有了密钥(私钥)，你才能解开信息。

2.工业领域

在汽车变速箱齿轮的设计中，可以将大小相邻两个齿轮的齿数设计成质数，以增加两个相同的齿在两个齿轮中相遇啮合的次数的最小公倍数，增强齿轮的耐久性，减少故障。

汽车顺序变速箱详图

3.生物领域

北美的周期性蝉(magic蝉)有着奇特的生命周期。它们每隔13年或17年就会成群爆发，这需要很长时间。

自17世纪中叶以来，科学家们一直对周期性蝉的生命周期感到困惑。它们遵循相同的基本生命周期:幼虫在地下生活13或17年，然后在夏季大量出现。它们爬树，蜕皮，长成成虫，然后在短短的几周内，成虫相遇，交配，产卵。孵化后，幼虫将返回地面，等待下一个周期。

为什么是13年或者17年，而不是其他数字，而且这个数字恰好是质数？

当这些周期性蝉大量出土繁殖时，周期性蝉的天敌吃得像一头猪，它们有更多的营养来繁殖，所以天敌的数量会大大增加。假设天敌只能性成熟六年，它们的后代再有六年也不会性成熟繁殖，因为没有周期性的蝉吃，它们的数量一直在下降。假设每周中蝉的周期是18年，那么在第18年天敌会继续疯狂的吃，在这个第18年的周期里会产生更多的天敌，这样每过18年，天敌的总数就会不断上升，周期性蝉的数量就会越来越少。同样，周期为16年的蝉很可能被周期为2年、4年、8年的天敌灭绝。

而13岁的蝉和17岁的蝉正好避开了这些可能，因为13和17是质数，除非天敌每年都繁殖，或者只是13、17年，否则无法帮助天敌繁殖。因为13年蝉和17年蝉选择了质数的生命周期，大大降低了帮助天敌繁殖的几率，使它们得以存活至今。

密集周期性的蝉趴在栅栏上。

数学美无处不在。就素数的特性而言，一方面，人类已经将素数分布的特性应用到计算机加密算法中；另一方面，自然界按照既定规律自然运行，但也产生了质数期的特征。壮年期的生物适应性最强，真的很神奇。这让人联想到斐波那契数列的松果和分形结构的山川(门户)。这与其说是大自然的神奇，不如说是数学规律的幕后指令的结果。

松果顺时针环8，逆时针环13，是斐波那契数列中的数字。