牛津通识读本：数学（中文版） [15]
既然近似乘法这么简单，近似平方也就很简单了——只要把原来的数替换为一个两倍位数的新数。由此得出，把n的位数减半可以求出n平方根的近似值。类似地，将位数除以3可以求出立方根的近似值。更一般地，如果n是个大整数，t是任一正数，那么nt的位数大约为n的位数乘以t。
关于对数呢？从近似的观点看它们其实极为简单：一个数的对数基本上就是它所包含的位数。例如，34587和492 348 797 548 735的对数分别约为5和15。
实际上，数一个数的位数所近似的是它以10为底的对数，即在便携计算器上按LOG键得到的数。通常，数学家谈论对数指的都是所谓的“自然”对数，也就是以e为底的对数。尽管e这个数的确很自然也很重要，但我们在此只要了解：一个数的自然对数，即在计算器上按LN键得到的数，大体上是它的位数乘以2.3上下。于是2 305 799 985 748的自然对数约为：13×2.3=29.9。（如果你了解对数，你会知道真正应当乘上的数是loge10。）
这一过程也可以反过来进行。假设你有一个数t且知道它是另一个数n的自然对数。那么数n称作t的指数幂，记作et。那么n大致是多少呢？刚才为了得到t，我们数n的位数并乘以2.3。所以n的位数必定约为t/2.3。这就决定了n的大小，至少是近似值。
我上面给出的近似值定义最主要的用途是作比较。例如，现在我们能够明显看出，对大数n而言，其对数要远小于立方根：比如，如果n有75位，它的立方根将会很大——大约有25位数，但它的自然对数则大约仅为75×2.3=172.5。类似地，数m的指数幂会远大于它的乘方，如m10。例如，若m有50位，那么m10大约有500位，但em大约有m 2.3位，远大于500。
对数字n=941 192施行不同的运算，得到的近似结果如下表所示。我没有包含进en，因为如果要这么做，那我就得给这本书换个名字了。
素数定理
素数是大于1且不能被其他整数——1和自身显然除外——整除的整数。小于150的所有素数有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， 101， 103， 107， 109， 113， 127， 131， 137， 139和149。小于150的其他数都可以做因子分解：例如91=7×13。（你可能会担心，将1排除在素数的定义之外似乎不合情理。这并不表达数的某种深层事实，只是碰巧成为一个有用的惯例，采纳这样的定义能使任意数被分解为素数的方式仅有一种。）
自从古希腊时期以来，素数就一直困扰着数学家们，因为它们表面上多多少少是随机分布的，但又并非全然随机。从没有人找出一种简单的规则，能够告诉我们第n个素数是多少（当然可以下番工夫列出前n个素数，但这算不上是简单的规则，而且当n很大时会很不切实际），几乎也不太可能会有这么一种规则。但另一方面，仅仅检查前35个素数，也能向我们透露一些有意思的特征。如果你算出相邻两个素数的差，那么你会得到下面这个新的序列：1， 2， 2， 4， 2， 4， 2， 4， 6， 2， 6， 4， 2， 4， 6， 6， 2， 6， 4， 2， 6， 4， 6， 8， 4， 2， 4， 2， 4， 14， 4， 6， 2， 10。（即1=3-2， 2=5-3， 2=7-5， 4=11-7等等。）这列数仍显得有些不规则，但这些数有一个趋势，大致可以看出它们逐渐在增大。显然它们不是稳定地增大的，但最开始的几个数都不大于4，而10和14这样的数直到后来才会出现。
如果你写出前1000个素数，那么相邻素数间距增大的趋势就会变得更加明显。也就是说，和小素数比起来，大素数的出现越来越稀疏。我们正可以预料到这一点，因为大数不成为素数的方式更多了。例如，可能会有人猜测10 001是素数，尤其因为它无法被2，3，5，7，11，13，17以及19整除——但实际上它等于73×137。
有自尊心的数学家绝不会满足于仅仅观察到（甚至没有得到严格地证明）大素数比小素数稀少。他一定想要知道，它们稀少到何种具体程度。如果你在1 000 001和1 010 000之间随机取一数，那么这个数有多大的机会是素数？换言之，1 000 000附近的素数“密度”是多大？它是极其小还是仅仅比较小？
没有接触过大学数学的人很少会提出这样的问题，其原因在于，他们没掌握将问题公式化表达并进一步思考所需的语言。不过，若是这章到现在为止你都看懂了，那么你就能够欣赏到数学中最伟大的成就之一：素数定理。定理陈述的是，在数n附近的素数密度约为1/logen，即1除以n的自然对数。
现在再来考虑1 000 001和1 010 000之间取随机数为素数的机会大小。这个区间内的数都大体等于100万。按照素数定理，密度因而约为1除以100万的自然对数。它以10为底的对数是6（在这个例子中，数位数会得到7，但既然我们知道精确答案，不妨使用精确值），所以自然对数约为6×2.3，即13.8。因此，1 000 001和1 010 000之间平均每14个数中有1个是素数，即略多于7 。相比之下，小于100的素数共有24个，即几乎占所有数的四分之一，这就说明了随着数的增大，素数密度是如何减小的。
既然素数分布有零零散散、颇似随机的性质，而我们却能证明其如此多的特点，这足以令人十分惊讶。有意思的是，关于素数的定理通常都是通过利用这种看似随机的性质得到证明的。例如，维诺格拉多夫在1937年证明的一个著名定理认为，任意充分大的奇数都可以分解为三个素数之和。我无法在本书中解释他是怎样证明的，但他绝对没有找出将奇数表达为三素数之和的方法。这样的思路几乎注定会失败，因为即使是生成这些素数本身也非常困难。基于哈代和利特伍德之前的工作，他大体按照下述办法来论证。如果你能够按照和素数分布同样的密度来真正随机地选取一些数，那么概率论的某种初步理论就能够表明，你几乎一定能够将所有充分大的数表示为你所取的这些数中的三个之和。实际上，你能够以多种不同方式进行这一分解。因为素数是类似于随机的（证明中较难的部分就是要说明，“类似于随机”是什么意思，再加以严格证明），它们的行为就相仿于随机选取的序列，所以所有充分大的数都是三素数之和——同样也以多种方式。为了解释这种现象，这里我们以35为例，列出它分解为三素数之和的所有方式：
35=2+2+31=3+3+29=3+13+19=5+7+23
=5+11+19=5+13+17=7+11+17=11+11+13
关于素数的很多研究都具有此类特点。你首先对素数设计一种概率模型，即假装告诉自己，它们是根据某种随机过程挑选出来的。接下来，在假设素数的确是随机产生的情况下，求证有哪些论断是正确的。这样可以使你猜测出很多问题的答案。最后，你努力表明，这个模型足够现实，能够保证你的猜测近似准确。要注意的是，如果强迫在论证中的每一步都给出精确答案，那这个思路就是不可能的。
很有意思，概率模型不仅仅是物理现象的模型，还能成为另一数学分支的模型。尽管素数的真实分布是严格确定下来的，可某种程度上它们看起来也像是实验数据。一旦这样看待它们，我们就很想去设计对应的简化模型，来预测特定概率论问题的答案是什么样的。这种模型有时的确曾使人们得到对素数本身的有效证明。
这种风格的论证取得了某些显著的成功，但它依然没能解决许多著名问题。例如，哥德巴赫猜想断言，任意大于4的偶数都可以表示为两个奇素数之和。这个猜想看起来比维诺格拉多夫所解答的三素数猜想要难得多。此外还有孪生素数猜想[1]，它声称有无穷对相距为2的素数，诸如17与19，137与139。表达这个问题的另一种方式是，如果你写出相邻素数之差，就像我之前做过的那样，那么2永远都会出现（尽管越来越稀少）。
数学中最著名的未决问题大概要数黎曼假设了。这个假设有若干种等价的表达形式，其中一种涉及素数定理给出的估计的精度。我之前说过，素数定理告诉我们在某数附近素数的近似密度。根据这个信息，我们可以计算出，不大于n的素数大约有多少。但这个“大约”有多“大约”？如果p（n）是不大于n的素数个数的真实值，q（n）是根据素数定理得到的估计值，那么黎曼猜想断言，p（n）和q（n）的差不会比大太多。如果能够证明这样的精度确实成立，那么它将会有很多的应用，但迄今所得到的结果比这要弱得多。
排序算法
数学另有一个分支领域，理论计算机科学，其中满是粗略的估计。如果有人要写一个计算机程序完成特定任务，那么程序当然运行得越快越好。理论计算机科学家提出了这样的问题：我们所能期望的最快速度是多快？
要精确地回答这个问题几乎总是不现实的，所以我们转而证明诸如“当输入规模为n时，这种算法的运行步数约为n2”这样的论断。由此出发我们可以总结出，一台普通的个人电脑有可能处理的输入规模（简言之，即你想要分析的信息量）为1000，而不是1 000 000。于是，这样的估计就有了实际的重要性。
计算机能够完成的一项非常有用的任务被称为排序，即将为数很多的对象按照给定标准排列顺序。举例来说，想象一下你想要根据喜好程度来排列一系列对象（不一定非要是无生命的，也有可能是一项工作的应聘者之类）。设想，你无法对每个对象赋予一数值来表示有多喜欢它，但是若给定任意两个对象，你总能确定更喜欢哪一个。再设想，你的偏好是前后一致的，意思是指，永远不可能出现这样的情况：喜欢A胜于B，喜欢B胜于C，又喜欢C胜于A。如果你不想为这个任务花太多时间，那么将比较次数最小化就会很有意义。
当对象很少时，很容易看出要怎样做。比如有两个对象，那你至少要作一次比较，一旦比较了你也就知道了它们的排列顺序。若有三个对象A、B、C，那