素数定理简史

素数就是没有真因子的正整数，比如2，3，5，7等等。大家学编程之初，免不了要设计一个方法求一个数是否是素数，或者输出小于定于给定参数的全部素数。素数定理呢就是描述这第二个问题的：素数是如何分布的，或者说给定一个比较大的数，有多少个比它小的素数。

研究素数一直是数论学家的最大兴趣，比如高低闻名但没什么用处的哥德巴赫猜想、有一定理解难度的黎曼猜想等。另外咱们编程界也广泛使用的RSA加密算法也是基于素数和余数原理的。

研究素数免不了要解决的首要问题是素数是有限还是无穷的。素数的无穷性比较容易证明，甚至我在面试求职码农的时候也提过这个问题，在引导下都能答出來。

求素数的（常规）方法不少，在小学生就能读懂的《漫游自然数王国》一书中介绍了很多筛法，通俗易懂，用法简单。在《素数之恋》一书中则比较完整的讲了近代大数学家们对素数分布的研究。

哪怕我们不是数学家，甚至我们可能只完成了义务教育阶段，但是完整写出100以内的素数应该也不是问题：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

这里一共有25个素数。
如果你能继续往下写，比如写到1000，你会发现按整百分组的话，每一组里面的素数越来越少。401到500之间只有17个，901到1000则有14个：

401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 599

907 911 919 929 937 941 947 953 967 971 977 983 991 997

你可能也注意到有时候相邻素数只相差2，这样的素数对称为“孪生素数”，也是数论学家的钟爱

再往大分布会更少，比如一万亿的最后一个整百分组里面只有4个素数：

999 999 999 937, 
999 999 999 959, 
999 999 999 961, 
999 999 999 989

因为上面说过素数是无穷的，所以不可能存在最后一个素数。所以数学家的目标就变成是否能找到一种方法预测素数的稀疏趋势？

黎曼的论文

1859年8月，刚满33岁的黎曼被任命为柏林科学院院士。对于年轻的黎曼说来，当上院士是崇高的荣誉。不过按照惯例，当选院士要提交一篇论文。于是黎曼写了《论小于一个给定值的素数的个数》。从此，数学跟以前不一样了！

那么小于给定值的素数有多少呢？我们先数一下：

N	小于N的素数个数
1 000	168
1 000 000	78 498
1 000 000 000	50 847 534
1 000 000 000 000	37 607 912 018
1 000 000 000 000 000	29 844 570 422 669
1 000 000 000 000 000 000	24 739 954 287 740 860

这里好像一下子看不出来有稀疏趋向。不过如果没有稀疏的话，最下面一行的个数应该是 168 000 000 000 000 000 000，现在的结果是它的七分之一。

有了这个映射，数学家当然希望将它转变为函数，就像咱们高一的时候一样。数学家将这个函数称为“素数计数函数”，用π(N)表示。比如π(100)=25, π(1000)=168。

接下来怎么办？数学家尝试了用自变量除以函数值看看：

N	小于N的素数个数	自变量与函数值的比
1 000	168	5.9524
1 000 000	78 498	12.7392
1 000 000 000	50 847 534	19.6665
1 000 000 000 000	37 607 912 018	26.5901
1 000 000 000 000 000	29 844 570 422 669	33.6247
1 000 000 000 000 000 000	24 739 954 287 740 860	40.4204

数学家惊呆了！为啥？因为他看到自变量每扩大1000倍，比值总是增加大约7。如果你也对数很敏感的话（其实高中生就可以），你发现这不正是对数的性质吗？

我们把对数、以及对数和比值的差距加进来：

N	小于N的素数个数	自变量与函数值的比	ln N	误差(%)
1 000	168	5.9524	6.9077	16.0490
1 000 000	78 498	12.7392	13.8155	8.4487
1 000 000 000	50 847 534	19.6665	20.7232	5.3731
1 000 000 000 000	37 607 912 018	26.5901	27.6310	3.9146
1 000 000 000 000 000	29 844 570 422 669	33.6247	34.5378	2.7156
1 000 000 000 000 000 000	24 739 954 287 740 860	40.4204	41.4465	2.5386

这样就得到了“素数定理”（the Prime Number Theorem，PNT）:

PNT: 素数计数函数趋近于N/lnN

PNT 有两个跟它等价的推论：

N 是素数的概率趋近于1/lnN
第N个素数趋近于NlnN

尽管素数定理的获得实际上经历了无数数学家们的辛勤努力，但是却少有人名被记录下来。因为不像爱因斯坦独自发现广义论，或杨振宁带领一个博士生就创立杨米尔斯理论，素数定理是经过太多数学家的合理总结出来的。不过如果要选数学家的名字记录下来，高斯一定是第一个。

高斯和勒让德

高斯（1777-1855）有一个称号是“数学王子”，关于他有一个广为人知的传说就是将1累加到100的和：这个传说多数数学家都愿意认为它是真的。

高斯也一直在研究素数，不过他本人不喜欢发表东西，关于素数的研究成果也只是和友人们聊聊。这有点类似于牛顿发明了微积分却没有公布，等到莱布尼茨发表后追悔莫及。

数学家勒让德1806年发表了他研究的最小二乘法，之后1809年出版的一本书中高斯提到自己1794年就找到了这种方法。虽然有大量文字材料能证明高斯没说谎，但是勒让德还是大发雷霆（不过比不上牛顿对莱布尼茨那样）。主要原因就是高斯没有发表他的发现。

1849年高斯在给天文学家恩克的信中（高斯自1807年底到哥根廷大学任天文台负责人，直到离世）说：

...使我想起我自已在同一个课题上的工作，这在很久以前就开始了，那是1792或1793年...。我最初做的事情之一是把我的注意力集中在不断降低的素数分布率上，为此我计算了几个一千中的素数分布,并把结果记在所附的白页上。我很快就发觉，尽管有波动起伏,但这个分布率平均地接近于其对数的倒数...。我经常(因为我没有耐心在这方面做持续的计算)在这里或那里用空闲的一刻钟计算另一个一千；但是我最后在快要做到一百万时放弃了。

后人数学家们在看到这封信是被震惊了：1792年高斯才15岁，当时连计算器都没有，仅有的数学工具是829以内的素数表，高斯就用纸和笔计算了接近100万以内的全部素数。其他数学家有人做了尝试，很快就放弃了：太痛苦了！而高斯仅仅是在消遣“一刻钟”！当然最有价值的部分是他在信中明确提到他发现了后人称为的素数定理。

更神奇的是，公认的第一部公开发表了素数定理的数学家是勒让德。1798年勒让德在他的书中提到了：

[pi(x)sim frac{x}{A ln x+B} ]

后来改进为

[pi(x)sim frac{x}{ ln x - A}, A approx 1.08366 ]

多年以后高斯给恩克的信中也讨论了勒让德这个结论，他认为1.08366是不对的，不过没给出自己的值。

如果勒让德还活着并且看到了这封信，一定会再次火冒三丈，估计杀了高斯的心都有了

欧拉

瑞士数学家欧拉是前无古人后无来者的数学大家，他晚年失明；但是对于很复杂的问题他心算的速度都比别人使用纸笔要快。欧拉是唯一一位有两个常数用他命名的数学家，一个是自然对数的低e = 2.71828...（e就是他名字的首字母），另一个是欧拉常数γ = 0.57721...（调和级数的和与自然对数对应项的差值收敛于欧拉常数，神奇不神奇）:

[ gamma = lim_{n ightarrow infty }[(sum_{k=1}^{n}frac{1}{k})-ln n] ]

欧拉（1707-1783）一生过得很艰难，常年被军警监控；30岁左眼失明，60岁全盲；13个孩子只有5个活到成年，其中还有2个比欧拉死的早；69岁时妻子去世，一年后他娶了妻子的妹妹

欧拉的第一个伟大贡献是巴塞尔级数：

[1+frac{1}{2^2}+frac{1}{3^2}+frac{1}{4^2}+cdots ]

这个级数是调和级数每一项的平方和。它收敛吗？

数学家们观察了很久，认为它收敛在1.644和1.645之间。但是具体值是多少，当时提出了悬赏（免费的），看谁能找到它的具体值。1735年，这个问题公布46年后，欧拉给出了答案：

[frac{pi^2}{6} ]

这个答案让当时所有的数学家吃了一惊：为什么会出现π，这里又没有圆，这个问题又不是一个几何问题：π来这干什么？

现在已经有很多级数的结果都是和π相关的，比如https://wenku.baidu.com/view/0a8cfd00a6c30c2259019e95.html?re=view#opennewwindow

更进一步，当时欧拉给出了调和级数项的指数是偶数的所有级数和（不一定以具体的形式）：

[1+frac{1}{2^4}+frac{1}{3^4}+frac{1}{4^4}+cdots = frac{pi^4}{90} ]

[1+frac{1}{2^6}+frac{1}{3^6}+frac{1}{4^6}+cdots = frac{pi^6}{945} ]

欧拉自己一直计算到了指数是26的级数和：

[1+frac{1}{2^{26}}+frac{1}{3^{26}}+frac{1}{4^{26}}+cdots = frac{1315862 pi^{26}}{11094481976030578125} ]

当指数是奇数时欧拉不知道结果是什么，一直到1978年科学家才证明奇数次幂的级数和是无理数。调和级数和超调和级数统称p级数，更多可以了解https://baike.baidu.com/item/p%E7%BA%A7%E6%95%B0

但是这和素数有什么关系？这个要通过下面要说的黎曼猜想关联起来。

狄利克雷

狄利克雷是黎曼的老师，他的贡献之一是证明了一个高斯的猜想：对于任意的无穷等差数列，如果首项和公差都是整数（这个简单，高中就学了），而且它们互质，那么这个数列包含无穷多素数。

后来人们发现了与这个定理相关的更有趣的现象：随便找一个正整数（比如9），找出比它小的全部互质的数（9的互质数有1，2，，4，5，7，8）。用9做首项，分别用这些互质数做公差构造数列（得到6个数列）。则这些数列内有相同的素数分布。当到达N时，N以内分布在数列上的素数个数是

[frac{1}{6} frac{N}{ln N} ]

狄利克雷当时对高斯的《算术研究》非常有兴趣。后来他听说了欧拉研究的巴塞尔级数的结论，觉得它们似乎可以放一起研究。

《算术研究》是研究同余算术的，高斯是同余算术大师。比如在钟表上8点+9点是5点，就写作8+9≡5(mod 12)，读作“8加9与5关于模12同余”。同余算术是比较难的一门算术

黎曼是狄利克雷的弟子，他的博士生导师是高斯，他在自己的文章中表达过过对高斯和狄利克雷比较推崇。

高斯于1855年离世，4年后狄利克雷去世。两位最尊敬的老师在这么短时间内先后去世，不得不说黎曼是受到严重打击的。而在这4年间，黎曼的父母、姐妹、老婆也都先后去世，更让黎曼觉得世事孤独。1866年（狄利克雷去世7年后）黎曼离世时还不到40岁。

黎曼级数也是p级数，只不过由于习惯，大家常把自变量使用s表示：

[zeta(s) = sum n^{-s} ]

前面也知道，当s大于1时级数收敛。下面是前几个级数和：

N	前12位级数和
1	发散
2	1.644934066848
3	1.202056903159
4	1.082323233711
5	1.036927755143
6	1.017343061984

黎曼主要考虑的自变量连续的情况，而不是前面我们看到的几个离散整数值。当s>1时，黎曼函数的图像有点像第一象限的反比例函数：自变量越大，值无限接近1；自变量从右侧接近1，值会无限大。

其他区域呢？当s=1时就是调和级数，发散；当s=0呢，是所有项都是1，明显也发散。s=1/2时，是所有自然数算术平方根的倒数和：

[zeta(frac{1}{2})=1+frac{1}{sqrt{2}}+frac{1}{sqrt{3}}+cdots>1+frac{1}{2}+frac{1}{3}+cdots ]

所以也发散。负数呢？比如-1：

[zeta(-1)=1+2+3+cdot ]

全体自然数的和，也发散。

可能有人会说：全体自然数的和哪里发散了，不是-1/12吗，哈哈

可能还有人说：黎曼函数的定义域不是0到1吗，为什么反而大于1的时候有值，小于1没有值呢...

欧拉积公式

现在我们对黎曼函数做一些处理：从第一个素数2开始，给黎曼函数两边乘以以素数做底、自变量做指数的倒数：

[frac{1}{2^s}zeta(s)=frac{1}{2^s}+frac{1}{4^s} + frac{1}{6^s}+cdots ]

得到了原式中的全部偶数项。现在用原式减去它得到全部奇数项：

[zeta(s) - frac{1}{2^s}zeta(s) \=underline{ (1-frac{1}{2^s})zeta(s)= 1+ frac{1}{3^s}+frac{1}{5^s} + frac{1}{7^s}+cdots } ]

接下来使用第二个素数3的指数去乘上式（刚才用的2的指数）：

[frac{1}{3^s}(1-frac{1}{2^s})zeta(s)= frac{1}{3^s}+frac{1}{9^s} + frac{1}{15^s}+ frac{1}{21^s}+cdots ]

继续用原式减去这个结果，得到所有不是2或3的倍数的项：

[(1-frac{1}{2^s})zeta(s)-frac{1}{3^s}(1-frac{1}{2^s})zeta(s)\= underline{ (1-frac{1}{3^s})(1-frac{1}{2^s})zeta(s) =1+frac{1}{5^s}+frac{1}{7^s}+frac{1}{11^s} + frac{1}{13^s}+frac{1}{17^s}+cdots } ]

接下来用同样的方法把5的倍数的项也去掉，两边都乘5的指数：

[frac{1}{5^s}(1-frac{1}{3^s})(1-frac{1}{2^s})zeta(s)= frac{1}{5^s}+frac{1}{35^s}+frac{1}{55^s} + frac{1}{65^s}+frac{1}{85^s}+cdots ]

上下相减，得到所有不是2、3、5的倍数的项：

[underline{ (1-frac{1}{5^s})(1-frac{1}{3^s})(1-frac{1}{2^s})zeta(s)= 1+frac{1}{7^s}+frac{1}{11^s} + frac{1}{13^s}+frac{1}{17^s}+cdots } ]

大家已经应该能非常清晰的看明白这个过程了：就是用埃拉托色尼筛法把前面任意项素数干掉。比如我们一直处理到素数997：

[ (1-frac{1}{997^s})(1-frac{1}{991^s})cdots(1-frac{1}{5^s})(1-frac{1}{3^s})(1-frac{1}{2^s})zeta(s)\= 1+frac{1}{1009^s}+frac{1}{1013^s} + frac{1}{1019^s}+frac{1}{1021^s}+cdots ]

如果自变量s是大于1的，那上式的值就是略大于1的一个数。比如s=3时值是1.00000006731036081534...所以是不是有可能当上面筛的过程足够长（无限长）就能得到

[cdots(1-frac{1}{11^s})(1-frac{1}{7^s})(1-frac{1}{5^s})(1-frac{1}{3^s})(1-frac{1}{2^s})zeta(s)=1 ]

因为左边每乘一项，右边就少一项（实际少的是一个素数和一些合数），一直搞下去右边1以外的项都到左边了。

现在把左边黎曼函数的系数移项到右边：

[zeta(s)=frac{1}{1-frac{1}{2^s}} imesfrac{1}{1-frac{1}{3^s}} imesfrac{1}{1-frac{1}{5^s}} imesfrac{1}{1-frac{1}{7^s}} imesfrac{1}{1-frac{1}{11^s}} imes cdots ]

也就是说，我们有：

[sum n^{-s} =prod_p (1-p^{-s})^{-1} ]

其中，n是全体自然数，p是全体素数。

上面这个式子也说明了素数有无穷多个，因为如果素数有限，那么右面就是个能够算出来的值；但是左边有可能是调和级数会发散的

上面这个将全体正整数和转换为全体素数积的式子就是“欧拉积公式”。

改进版素数定理：对数积分公式

要继续研究素数定理，这里需要引入一个新的函数：

[ln ^ {-1} t ]

的积分：

[int_{0}^{x} frac{1}{ln t} dt ]

这个积分不能使用我们已知的其他普通函数表达，所以数学家为了方便，将它命名成

[Li(x) ]

这个函数就是对数积分函数。它的定义域是除1外的所有正数，图像如下（横轴被拉长了，所以图像有点矮，在1.451369...处值为0）：

为什么Li(x)重要呢？因为它是比前面我们说的N/ln N对π(x)更好的估计。所以这里重新表述一下素数定理：

改进版PNT: π(x)趋近于Li(x)

另外对于所有的x，

[Li(x) > pi(x) > frac{x}{ln x} ]