厄拉托西尼(4)〈历史上第一位测量地球圆周的人〉江铭辉 五梦网

(六) 厄拉托西尼筛

自然数可分为三类即1、质数和合成数三类，质数只有1和本身是因子外，并没有其他因子，而合成数则有两个以上大于1的因子。所谓质数表就是造一张表，包括所有不超过已知自然数N的所有质数。如果有一个数m，若不被所有小√m之整数整除，则m本身必为一质数。厄拉托西尼巧妙利用这个原则。发明一种制作质数表的方法，使他的大名在数学史上永垂不朽。这方法虽然简单，但到今天仍旧适用。其制作方法如下：

首先，把1以外的正整数2,3,4,5,……依序写下来。

最初的数2为质数。但是，在其后出现的2的倍数都是合成数而非质数。因此，只留下最初的2，而把在其后面出现的2的倍数的数字（譬如4,6,8……）全部删除。

下一个数3是质数。但是，在其后出现的3的倍数都是合成数而非质数。因此，只留下3，而把在其后面出现的3的倍数的数字都删除。

其次4这个数已经被消去，它不是质数。再下面的数5，即不是2的倍数，也不是3的倍数，而为质数。因此把5留下，而把在其后面出现的5的倍数的数字全部删除。

若如此继续做下去而到达某一个质数P，则小于 的自然数中不被消去而留下的，都是质数。现在我们以100的质数表为例，说明如下：

图10是一个用厄拉托西尼筛的方法制作的100以下质数表。

图10：用厄拉托西尼筛的方法制作的100以下质数表。

制作此表，我们只要把10以下的质数的倍数（即2、3、5、7的倍数）删除就可以，因为10的平方是100，我们用不着再继续作10到100的删除工作。

从理论上说，用厄拉托西尼筛法可以造出任意范围内的质数表，厄拉托西尼自己就曾造出第一张1000以下的质数表（如图11）。

图11：厄拉托西尼制作的1000以下质数表。

尽管用厄拉托西尼筛可作成任意数目的质数表，但是质数的数目究竟是有限或无限大？这个问题早在厄拉托西尼筛发明以前，希腊数学界就出现了一场关于质数是有限个还是无限个的辩论，那时希腊的知识分子很喜欢辩论，而且喜欢通过数学证明来决定胜负。最后由欧几里德（Euclid）在他的〈原本〉书中证明了质数有无穷多个，来结束这场争论。欧几里德的证明方法很简单，他说：如果质数的个数有限，那么我们就可以把它一一写出来，譬如：P₁、P₂、P₃、P₄……P_n，但是我们看P₁×P₂×P₃……×P_n+1这个数，显然不能被P₁、P₂、P₃、……P_n，中的任何数整除，因此除了P₁、P₂、P₃……P_n外，还有一个更大的质数存在。所以质数的个数无限多。

质数既然是无穷多个，有没有公式将所有质数的分布表示出来。十八世纪以前许多数学家都尝试给出质数的表示式，结果都失败了。

公元1792年，年仅15岁的德国数学家高斯（C.F. Gauss）以刚出版的兰伯特（J.H. Lambert）质数表为蓝本，研究质数的分布。在这里我们依数学家兰道（E.G.H. Landau）以后的惯例，把整数X以前的质数个数写成π(X)。高斯先把1000分成一组，根据质数表计算各组里面的质数的个数，发现 （ln t为自然对数）。很巧合地，法国的数学家勒建德（A.M. Legendre）（图12）在这时候也根据图13的质数个数分布表，发现了下面的近似公式，并在1798年发表。

图12：勒建德（A.M. Legendre，法国人，公元1752～1833年）1798年，他发表专着〈关于数论的研究〉并第一个提出“数论”这个名词，其后他又提出 的质数个数猜想，1823年证明了费马大定理n=5是成立的，他也研究〈椭圆函数论〉及欧几里德〈原本〉第五公设皆有成就。但他最著名的应是广泛应用在工程及物理学的“勒建德方程式”（Legrendre equation）勒建德和拉格朗日（J.L. Lagange，法国人，公元1736～1813年）、拉普拉斯（P.S. Laplace，法国人，公元1749～1827年）称为法国数学界的“3L”。

这两个式子是否成立，两位德国和法国的数学名家对他们自己所发现的质数分布公式都无法证明其是否成立，可见证明它的困难度。最后人们称 为质数猜想。

图13： 10⁹以下的π(x)及x/ln x

公元1859年，德国科学院青年院士黎曼（G.F.B. Rieman），他以复变函数理论为工具尝试对质数猜想作出证明，可惜没有成功。尽管黎曼当时没有解决，但他所出的复变函数方法，被希尔伯特（D. Hilbert）（图14）列为23个世界级数学难题之一。且为后人奠定了质数猜想证明的基础。三十年后，法国数学家哈达玛（Hadamard Jacques, 1865～1963）及比利时数学家瓦莱普辛（Vallee Poussin, 1866～1962）分别独自于1894年及1896年以黎曼复数函数为基础证明了质数猜想，即证明了 ，从此质数猜想变成了质数定理。

用复变函数这种高等数学来证明质数问题，总有些拐变抹角。它与整数中的质数有什么关系﹖有没有不用复数函数的初等证明方法。许多数学家连英国世界一流数学家哈代（Hardy, 1877～1947）都断言质数定理的初等证明是不可能的。

就在哈代断言28年之后，挪威和匈牙利的两位青年数学家赛尔伯格（Atle Selberg, 1917～　）及爱多斯（P. Erdos）同时用初等方法证明了质数定理。

图10：希尔伯特（德国人，1862～1943年），希尔伯特于1900年的巴黎第二届国际数学家大会提出著名的23个数学未解问题，扬示了20世纪数学家奋斗的目标，他研究几何学基础论，代数的整数论，也建立希尔伯特空间理论，晚年关心数学基础。透过符号逻辑及证明论的研究，建立数学的形式主义。