素数定理简史（一）
素数就是没有真因子的正整数，比如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
- 分享到
-
-
