质数（Prime Number）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

质数是非常神奇的数值概念。

定义

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

质数具有许多独特的性质

（1）质数p的约数只有两个：1和p。

（2）初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

（3）质数的个数是无限的。

（4）质数的个数公式 是不减函数。

（5）若n为正整数，在 到 之间至少有一个质数。

（6）若n为大于或等于2的正整数，在n到 之间至少有一个质数。

（7）若质数p为不超过n（n≥4）的最大质数，则p>n/2。

（8）所有大于10的质数中，个位数只有1,3,7,9。

应用

质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若 没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

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

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。

质数的孤独

《质数的孤独》是意大利八〇后作家、粒子物理学博士保罗·乔尔达诺的处女作，2008年出版后，即获得意大利最高文学奖斯特雷加奖，并迅速成为欧美超级畅销书，迄今在欧洲销量已超过500万册。同名电影于今年9月在威尼斯电影节首映。

马蒂亚是一个年轻的数学天才，他相信自己是质数中的一个，而中学同学爱丽丝正是他的孪生质数。他们都有痛苦的过往，同样孤独，同样无法拉近和其他人之间的距离。从少年到成年，他们的生命不断交叉，努力消除存在于彼此间障碍，相互影响又彼此分离，就像孪生质数，彼此相近却永远无法靠近。

引自第631页：

质数只能被一和它自身整除。在自然数的无穷序列中，它们处于自己的位置上，和其他所有数字一样，被前后两个数字挤着，但它们彼此间的距离却比其他数字更远一步。它们是多疑而又孤独的数字，正是由于这一点，马蒂亚觉得它们非常奇妙..... 在大学一年级的一门课上，马蒂亚知道，在质数当中还有一些更加特别的成员，数学家称之为“孪生质数”，它们是离得很近的一对质数，几乎是彼此相邻。在它们之间只有一个偶数，阻隔了它们真正的亲密接触，比如十一和十三，十七和十九，四十一和四十三。假如你有耐心继续数下去，就会发现这样的孪生质数会越来越难遇到，越来越常遇到的事那些孤独的质数，它们迷散在那个纯粹由数字组成的寂静而又富于节奏的空间中。此时，你会不安地预感到，到那里为止，那些孪生质数的出现只是一种偶然，而孤独才注定是它们真正的宿命。然而，当你正准备放弃的时候，却又能遇到一对彼此紧紧相邻的孪生质数。因此，数学家们有一个共同的理念，那就是要尽可能地数下去，早晚会遇到一对孪生质数，虽然没有人知道它们会在哪里出现，但迟早会被发现。

引自第1483页：

那些我们不爱的人对我们的爱只停留在表面，很快就会挥发掉。

质数螺旋

质数螺旋（ Ulam spiral — “乌拉姆螺旋”）

1963 年，美籍波兰裔数学家乌拉姆（S.Ulam）在聆听一场无聊的报告时在纸上信手涂鸦。他从纸的中心开始，由内而外螺旋形撰写了各个正整数。随后，他圈出了其中所有的质数，如图 3.7 所示。令乌拉姆吃惊的是，这些被圈出的质数与整数方阵的对角线趋近于平行。乌拉姆进一步绘制了一个大小为 200×200 的质数方阵，如图 3.8 所示。他发现，在质数方阵中可以清晰地观察到水平线、垂直线、对角线似乎都包含更多的质数。同时，其他质数的分布似乎还满足螺旋线的关系。

▲ 图 3.7：乌拉姆在纸上的信手涂鸦

▲ 图 3.8：大小为 200×200 的质数方阵

在知乎问题“极坐标表示 5000 到 50000 之间的素数为什么会形成一条斐波那契螺旋线？”中，知友@王小龙使用 Matlab 软件绘制出了漂亮的质数螺旋线图(上图所示)。

我们不看 500 到 50000 间那么多的质数了，看 500 到 1500 之间的质数就够了。把质数涂成蓝色，把合数涂成红色，就得到如图 3.9 的图像。

▲ 图 3.9：500 至 1500 中的全部质数与合数

发现了吧，大概 11 点钟方向和 5 点钟方向的确各有三列数全是合数。如果还是看不太清楚，把 500 到 20 000 内的质数和这三条全是合数的线画出来，如图 3.10 所示。

▲ 图 3.10：500 至 20000 中，所有合数所构成的 条螺旋线

如果把所有没有质数的螺旋画出来，应该如图 3.11 所示。

从维基百科的质数页面链接到一个提供质数表的网站，下载了前 100 万个质数。现在把区间[1 006 721,15 485 863]之间，也就是 100 万到 1500 万之间的质数画出来，如图 3.12 所示。

▲ 图 3.12：1006721 至 15485863 中，所有质数所构成的螺旋线

把左边部分放大一点看，如图 3.13 所示。

▲ 图 3.13：1006721 至 15485863 中，所有质数所构成螺旋线的左上放大结果

第二个可以观察到的现象就涉及孪生质数猜想了。前文曾介绍过，前 x 个正整数中大约有 x/lnx 个质数。这也就意味着，随着 x 的不断增大，质数的比例会越来越小，质数在整数间的分布会变得越来越稀疏。例如，当 x=1000 时，lnx≈7，即大约每 7 个整数中就有 1 个质数；当 x=10000 时，lnx≈9，大约每 9 个整数中才有 1 个质数；当 x=100000 时，lnx≈12，大约每 12 个整数中才能找到 1 个质数。实际上，给定任意整数 n>1，则连续 n 个整数(n+1)!+2,(n+1)!+3,,(n+1)!+(n+1)都是合数，因为显然这 n 个整数从前到后可以分别整除 2,3,…,n+1。

那么，一个很自然的问题是，是否质数越大，质数与质数之间就会隔得越来越远呢？其实不然。很多情况下，两个连续的质数之间只相差 2。所谓【孪生质数】（Twin Prime），就是指相差为 2 的两个质数。孪生质数用数学语言描述为：整数对(p,p+2)，其中 p 和 p+2 均为质数。列举一下最小的 20 对孪生质数：(3,5)、(5,7)、(11,13)、(17,19)、(29,31)、(41,43)、(59,61)、(71,73)、(101,103)、(107,109)、(137,139)、(149,151)、(179,181)、(191,193)、(197,199)、(227,229)、(239,241)、(269,271)、(281,283)、(311,313)。截至 2020 年 10 月，人类已知最大的孪生质数为：(2996863034895×21290000-1,2996863034895×21290000+1)

如果用十进制表示这一对孪生质数，则需要 388 342 位。

那么，孪生质数是否也像质数本身一样有无穷多个呢？希尔伯特在 1900 年第二届国际数学家年会上的报告中正式提出了孪生质数猜想，并将此猜想列入了 23 道最为重要的数学问题中：存在无穷多个质数 p，使得 p+2 也是质数。1849 年，法国数学家波利尼亚克（A. Polignac）提出了一个比上述猜想更一般化的猜想，称为【波利尼亚克猜想】（Polignac’s Conjecture）：对所有自然数 k，存在无穷多个质数对(p,p+2k)。当 k=1 时，波利尼亚克猜想与孪生质数猜想等价。

孪生质数猜想虽然不如哥德巴赫猜想那样著名，但在数学界仍然是一个公认的难题。幸运的是，孪生质数猜想有望在近期得到解决。2013 年 5 月 14 日，据《自然》（Nature）杂志报道 ，华人数学家张益唐证明：存在无穷多个质数对，使得质数对中前后两个质数的差值小于 7000 万。他的论文已被国际数学旗舰期刊《数学年刊》（Annals of Mathematics）于 2013 年 5 月 21 日接收，并于 2014 年正式发表 。同期，华人数学家陶哲轩于 2013 年 6 月 4 日开始了一个名为“PolyMath”的计划 ，邀请网上的志愿者协助合作，降低张益唐的论文中所给出的 7000 万上限。截止至 2016 年 7 月 14 日，上限已经从 7000 万降低至 246。

上文节选自知乎Book《密码了不起》, 作者刘蔚然，[遇见]已获出版社授权