1.4 关于素数的那些事

难度：★★★

素数也叫作质数，是除了1和它自身之外不能被任何数整除的数。例如2、3、5、7、11…这些都是素数，因为这些数包含的因数只有1和它们自身之外再无其他。而4、6、8、9、10…这样的数就不是素数，人们称它们为合数。需要注意的是，1既不是素数也不是合数。

算术基本定理告诉我们：任何一个自然数要么是素数本身，要么可以分解成有限个素数的乘积（即所谓的分解质因数），并且这种分解是唯一的。例如，合数6就可以分解成2×3，而且只能分解成2×3，其中2和3都是素数。请注意，6=1×2×3不是分解质因数，因为1不是素数。

因为素数具有这样基础的性质，所以数学家们常说：“如果把所有的数字比喻成一座大厦，那么素数便是构成数字大厦的砖块和基石”。也正因如此，素数在数学中，特别是在数论及密码学中有着举足轻重的地位。从古至今，数学家们对素数都抱有十分的兴趣，在他们研究素数的过程中发现了有关素数的许多规律和特性，同人也给后人留下了一个又一个素数的谜团。下面我们来看一下关于素数的那些事。

怎样得到素数

既然素数如此重要，我们怎样才能在浩瀚的数字海洋中得到素数呢？

获取素数最简单直观的方法就是根据素数的定义判断一个数是否是素数，如果它是素数，就将这个数收集起来；否则就跳过该数，继续判断下一个数。这种获取素数的方法称为“穷举法”或“穷搜索法”。例如，要找出1～10之间的素数就可以使用这种方法，如图1-20所示。

虽然穷举法简单直观，但是效率很低。首先此方法需要判断给定范围内的每一个自然数是否是素数，而素数在自然数中所占的比例是很小的，所以这种方法将大量的时间和运算都消耗到了判断一个数是不是素数上，而不是寻找素数。

其实人们很早就发现了更为巧妙和高效的获取素数的方法，这就是筛法。

筛法是公元前300年左右由古希腊数学家埃拉托色尼提出的，因此也叫作埃拉托色尼筛法（The Sieve of Eratosthenes）。用筛法获取素数的基本思想是：将给定的自然数从小到大排列，然后选取里面最小的素数，将其倍数“滤掉”，然后再找到下一个素数，将其倍数“滤掉”，以此类推，直到将给定范围的自然数中所有素数的倍数全部“滤掉”，剩下的就都是素数了。这个过程就好像用一个筛子对给定范围内的自然数进行过滤，滤掉其中所有的合数，剩在筛子里的数就都是素数了。图1-21所示为利用筛法获取1～10范围内的素数的过程。

利用筛法获取素数的效率要比穷举法高很多。在筛取素数时只需要找出第一个素数（例如2），之后就是删除该素数的倍数（例如4、6、8、10），待全部删完后再取的下一个数无须判断则一定是素数（例如3），只需要将这个素数的倍数（例如9）删除即可。埃拉托色尼筛法获取小于n的素数的时间复杂度约为O（ n log logn），而穷举法的时间复杂度要达到O（ n²）。

素数到底有多少个

自然数的个数是无穷的，人们又可以通过筛法从自然数中筛选素数，所以人们自然会想到这样一个问题：素数的个数是否也是无穷的呢？其实这个问题早在2000年前古希腊数学家欧几里得（见图1-22）就已经给出了答案——素数的个数是无穷的。

欧几里得在他的名著《几何原本》中记载了证明素数个数无穷的方法，证法如下。

假设素数是有限的，且最大的素数是P。设Q=（2×3×5×…×P）+1，因为P是最大的素数，同时Q＞P，所以Q一定是一个合数。又因为Q整除所有的素数后都余1，即Q整除2余1， Q整除3余1，…， Q整除P余1，所以Q不能被任何素数整除，因此Q必然是一个素数。所以P就不是最大的素数，这与假设是矛盾的，因此素数有无穷多个。

可见跟自然数一样，素数的个数是无穷的。也正因为有无穷多个素数，人们才能在素数的世界里继续探索下去。

素数是怎样分布的

素数有无穷多个这个论断早在古希腊欧几里得时代就给出了，但是素数在自然数中是如何分布的至今也未被人们完全掌握。我们能否写出一个素数的通式呢？如果能够找到素数的通式，素数的规律就大白于天下了。然而时至今日，人们也没能找到这样一个通式，所以有些人认为“素数就像杂草一样，没有人能够准确预测下一个素数会从哪里冒出来！”。但是也有一些人认为“素数是有其内在的分布规律的，只是人们尚未发现它”。2000多年来，大量的数学家绞尽脑汁，有的甚至终其一生心血来研究素数的分布规律，希望能揭开素数神秘的面纱。瑞士的数学家欧拉就是其中一位著名的先行者。

欧拉曾在给他朋友的一封信中写道“素数的计算公式在我们这辈子可能是找不到了，不过我还是想用一个式子来表达它，但并不能表示出所有素数， n²-n+41， n等于1到40”。欧拉给出的这个公式在n∈[1，40]都是正确的，但当n＞40时就不能保证正确了，所以这并不真正意义上的通式。后来欧拉又提出“如果用π（ x）表示小于x的素数的个数，则π（ x）≈x/lnx。”至此人们将素数研究的重点由通式转为计算素数的分布函数π（ x）。欧拉提出π（ x）的近似表达之后就没有再对素数进行更为深入的研究了，人们对素数的研究也始终没有进展。直到欧拉去世几十年后，数学天才高斯和同时代的数学家勒让德（见图1-23）相继提出了素数定理，人们对素数的分布才有了更加深入的认识。

素数定理给出了素数分布函数π（ x）的趋近公式，但是它的绝对误差非常大，以至于实际的作用非常小。直到1859年，高斯的学生黎曼（见图1-24）才给出了π（ x）的准确公式。

这是数学家黎曼在一篇名为“论小于某给定值的素数的个数”的论文中提出的公式，该公式形式非常复杂，其中还涉及一个超越函数的非平凡零点问题，正是该问题引申出了一个数学界著名的猜想——黎曼猜想。虽然在知名度上黎曼猜想不及哥德巴赫猜想和费尔马猜想那样出名，但是它在数学上的重要性却远超后两者。

著名的哥德巴赫猜想

人们在研究素数的过程中也发现了素数的许多有趣的特征和规律。这些特征和规律有些已经被人们弄清了原理，有些仍然是不解的谜团，等待着后来者探寻它们的深层原因。其中最为著名的一个谜团就是哥德巴赫猜想。

哥德巴赫猜想是德国数学家克里斯蒂安·哥德巴赫于1742年在写给欧拉的信中提出的一个猜想。这个猜想内容是：

1）任何一个大于2的偶数都可以表示为两个素数之和。

2）任何一个大于5的奇数是3个素数之和。

欧拉在回信中表示：他深信哥德巴赫的这两个猜想都是正确的定理，但他不能加以证明。于是哥德巴赫猜想成为数论领域的千古谜团。

因为通过猜想1）很容易推导出猜想2）的结论，所以猜想1）最为重要，现在人们熟知的哥德巴赫猜想就是猜想1）的表述。

如果把命题“任一充分大的偶数都可以表示成一个素因子个数不超过a的数与另一个素因子个数不超过b的数之和”记作“a+b”的话，哥德巴赫猜想其实就是要证明“1+1”的正确性。因此人们也习惯地称哥德巴赫猜想问题为“1+1”问题。

1900年，在法国巴黎召开的第二届国际数学家大会上，德国数学家大卫·希尔伯特为20世纪数学家建议的23个问题中，哥德巴赫猜想就是其中一个问题。然而时至今日哥德巴赫猜想仍未被人类攻克，它已然成为一个世界性的数学难题。

表1-1是哥德巴赫猜想证明的推进过程，人类在攻克哥德巴赫猜想的道路上充满了艰辛和曲折。在近半个世纪的研究和探索中，人们已将哥德巴赫猜想的证明从最初的“9+9”推进到“1+2”，走在最前面的是我国著名数学家陈景润（见图1-25）。

曾有人这样生动地比喻哥德巴赫猜想：“自然科学的皇后是数学，数学的皇冠是数论，‘哥德巴赫猜想’ 则是皇冠上的明珠。”陈景润就是离这颗明珠最近的人！

人们之所以热衷于研究素数，不仅仅因为素数是构成数字大厦的“砖块”和“基石”，更是因为素数中隐藏着太多奇妙的规律和未解之谜等待人们的探索。除了前面提到的黎曼猜想、哥德巴赫猜想之外，关于素数的著名猜想还有孪生素数猜想、梅森素数猜想、吉尔布雷斯猜想等，另外，神奇的素数螺旋的本质也一直没有被人们所理解。所以人们在素数的研究上仍有很长的路要走，或许素数真的就是宇宙留给人类的密码。