在数学中什么叫素数？程序员发现最大的素数

不到一年，第51个梅森素数就出人意料地被发现了。

2017年12月，第50个素数被发现。 美国普通电气工程师佩斯在担任GIMPS项目志愿者的第14年，发现了第50个梅森素数，即-1。

还记得当时，在第50个梅森素数诞生两周后，日本彩虹协会出了一本名为《2017年最大素数》（《The Prime in 2017》）的书。 约32mm，共719页，全书只印了一个数，第50个梅森素数。

《2017年最大质数》内页密密麻麻的数字

虽然数学书籍从未如此畅销，但这本书在发售两周后迅速攀升至日本亚马逊数学类“畅销书第一名”，并销售一空！

或许对于读者来说，将这本书买回家的精神意义远大于实际意义。

毕竟，从17世纪法国数学家马林·梅森开始，人们就一直在寻找梅森素数。 找到第50个梅森素数是数学领域的重大发现，也是人类发展的新里程碑。

这本书更多的是一种信仰，代表着人类不断进取、勇攀高峰的精神。

或许看到这里，有人会问，为什么科学家们如此热衷于寻找素数呢？ 质数有什么用？ 下面小天就和大家聊聊关于素数的一切。

什么是质数

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

这个定义很容易理解。 以小于10的自然数为例，2、3、5、7都是质数。 比如7只能分解成1乘以7，没有其他的分解方法。 对于其他数，比如8可以分解成2×4，所以8不可能是素数。

科学家之所以热衷于寻找素数。 一方面是追求自己的理想，孜孜不倦地攀登数学高峰。 但另一方面，质数在实际场景中体现出巨大的价值。

素数在计算机领域的应用无非就是信息的加密，其中就包括大名鼎鼎的RSA算法（小智之前写过RSA算法的介绍，点传送门）。 由于目前大整数因式分解，即求大整数的质因数是一件非常困难的事情。 目前除了暴力破解外，还没有找到其他有效的方法。 也就是说，只要密钥长度足够长，求素因数的时间就很长，用RSA加密的信息实际上是破解不了的。 因此，素数在密码学中扮演着重要的角色。

只有有了密钥（私钥）才能解密信息

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

汽车序列式变速箱详图

北美周期蝉 ( ) 具有奇特的生命周期。 它们需要很长时间，每 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圈，恰好是斐波那契数列中的数

数学家用质数做什么？

素数，就像数字的原子，是其他数字的基石。 自然数是无限的，那么作为基石的质数有多少呢？

这个问题在 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年挪威数学家布伦（Brun）证明了“9+9”后，这个公式就被各大数学家不断简化。 1966年，中国数学家陈景润证明了“1+2”。

素数查找程序 - 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月，美国数学家、程序员乔治·沃特曼（ ）编写了一个计算梅森素数的程序。 他把程序放到网上，供数学家和数学爱好者免费使用。 这是最初的互联网梅森素数搜索项目（Great Prime，GIMPS）。 任何拥有个人电脑的人都可以加入 GIMPS 并成为素数猎人。

从1997年到现在，所有新的梅森素数都是通过GIMPS分布式计算项目发现的。 这个项目已经成功的聚集了几十万台计算机来计算一个问题，其计算能力已经远远超出了我们的想象。

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

如何找到质数

素数去向不定，分布不明。 我们怎样才能找到素数？

公元前2世纪，希腊数学家埃拉托色尼（）提出了一种非常简单有效的素数筛法，我们称之为埃拉托色尼筛法（Sieve of ）。 核心是：要得到自然数n以内的所有素数，必须剔除所有不大于根号n的素数的倍数，其余为素数。

筛法的一个例子

具体筛选方法如下：

Step 1：确定需要筛选的质数范围，确定范围的最大值，比如120。 Step 2：120的平方根结果为10.95，所以只需要取其倍数即可11以内的所有质数，去掉120以内的数，剩下的就是质数。 先去掉2的倍数，去掉11以内的4、6、8、10，去掉120以内所有2的倍数第三步：最小的未去掉的数为3，去掉是3的倍数，去掉11以内的9，去掉120以内所有3的倍数。 第四步：最小未去掉的数是5，去掉5的倍数，不需要去掉120以内的数11，把120以内所有5的倍数的数都去掉。 ...以此类推，120以内的所有质数都可以完全找到。

不得不说，古人的智慧真是令人敬佩。

科普完素数知识后，超模突然发现，第50个和第51个梅森素数都是在12月发现的！

而新的一年即将到来，第52个梅森素数是否会被发现呢？ 让我们拭目以待。

郑重声明：本文版权归原作者所有，转载文章仅出于传播更多信息之目的。 如作者信息标注有误，请第一时间联系我们修改或删除，谢谢。