千米小说网

01 如何不去考虑数 How Not to Think About Numbers（第2页）

素数在数千年来一直深深吸引着人们[8]，因为它们无穷无尽（我们在下一章会证明这个说法），在自然数中现身的方式又神出鬼没。它们性质中神秘莫测的这一面在现代密码学（cryptography）中被加以运用，来保护互联网上的机密信息。这将是第4章的话题。

素性检验：素数整除性测试

为了找出不大于某个数（比如100）的所有素数，最容易想到的方法是把所有数写下来，再寻找并划掉里面的合数。基于这一思想的标准方法叫作埃拉托斯特尼筛法[9]（SieveofEratosthenes）。方法如下：首先圈出2并划掉列表里2的倍数（即其他偶数）。然后回到开始，圈出第一个尚未被划掉的数（即3），划掉剩下数表里它的所有倍数。重复这一过程足够多遍，剩下没有被划掉的就是素数。即便它们中一些被圈出来了，而另一些没有。例如，图1展示了对不大于60的数运用筛法的过程。

你怎么知道什么时候该停止筛选呢？重复这一过程，直至圈到一个数，大于整张表中最大数的平方根。比如，当你在不大于120的数中筛选素数时，需要筛掉2，3，5和7的倍数，接着当你圈出11，就可以停下了。因为112=121。此时，你已经圈到了第一个大于你的最大数（这里是120）的平方根的数，剩下的素数虽未被触及，但所有的合数都已经被划掉，它们都是2，3，5或7的倍数。

检测能否被2或5整除很容易，因为这两个素数是我们的底数10的素因数。看出这一点，你只需查看待检数n的最后一位：当且仅当个位为偶（即0，2，4，6或8）时n可以被2整除，当且仅当n最后一位为0或5时它含有因数5。不管数n有多少位，判断n是否为2或5的倍数，我们都只需检查最后一位。对于不能整除10的素因数，我们需要多做一点工作，尽管如此，仍然有一些整除性测试方法，比计算完整的除法更快捷。

一个数能被3整除，当且仅当其各位数字之和能被3整除。例如，数n=145373270099876790的各位数字之和是87，而87=3×29，因此n可被3整除。当然，我们还可以将这个测试应用于数87，然后继续在每一阶段都求出各位数字之和，直到结果显而易见。对于给出的例子这样做，可以得到以下数列：

145373270099876790→87→15→6=2×3。

你会发现，这里列出的所有整除性测试方法都如此快捷，你可以相对轻松地处理有几十位的数，甚至比手持式计算器能处理的最大的数还要大上数十亿倍。

下面要给出不大于20的剩下所有素数的整除性测试方法，因为它们都属于同一个类型。虽然它们成立的原因不那么明显，但是这些方法应用起来都很简单。即便这里没有收录论证，想证明它们的正确性并不是特别困难。

因此n可以被7整除。每执行一次指令循环，我们都至少能减少一位数，因此执行循环的次数大约与初始数的长度相同。

为了检测n是否有因数11，将原数的最后一位移除，再从新数中减去原数的最后一位，依此重复。比如，我们的方法揭示了下面这个数是11的倍数：

检测能否被13整除，将原数最后一位移除，再用新数加上原数最后一位的4倍，接着类似于7和11的方法，不断重复。比如，13是下面这个数的一个素因数：

接下来是17和19。对于17我们将原数最后一位移除，再用新数减去原数最后一位的5倍，重复操作直到可判断整除性；对于19我们将原数最后一位移除，再用新数加上原数最后一位的两倍，重复操作直到可判断整除性。例如，我们来检测18905是否能被17整除：

因而它不是17的倍数。但对于19，整除性测试给出了另一种结论：

拥有了这一组测试，你现在就可以检查不大于500的所有数的素性，因为232=529超过了500，因此19是你需要考虑的最大的素因数。例如，为了确定247的性质，我们只需要检查它是否能被不大于13的素因数整除，因为下一个素数的平方，172=289，超过了247。运用对13的测试，我们发现247→（24+28）=52→13，这是一个13的倍数（247=19×13）。

素数相乘可以得到无平方因数（square-free）的数，要想构造关于这些数的整除性测试，可以叠加并行其素数因子的整除性测试。比如，对于42=2×3×7，一个数n能被42整除，当且仅当n可以通过2，3和7的三项整除性测试。但是，对于那些有平方数因数的数，像9=32，则不能由此得到。顺便说一句，9是n的因数当且仅当9也是n的各位数字之和的因数。

你也许会问：数千年以来，那些聪明的数学家们难道还没有想出更好、更精妙的检测素性的方法？答案是有的。2002年，我们发现了一个相对快速的判断一个给定的数是否为素数的方法。不过，如果给定的数恰好是一个合数，那么这个所谓的“AKS素性测试”并不能给出该数的因数分解。虽然原则上说，找到一个给定数的素因数的问题可以通过试错来解决，但实际操作中，这对于很大的整数依然难以实现。正因为此，它构成了很多互联网加密方法的基础。我们会在第4章回到这个话题。在那之前，我们会在接下来的两章中更近距离地认识一下素数和因数分解。

[1]　这里的中文数字“六”强调的是“六”这个数本身的概念。

[2]　我国的自然数包含零，而本书的自然数不包含零。

[3]　1码等于3英尺等于36英寸。

[4]　或称因子、约数，英文也可以写作divisor。

[5]　英文也可以写作prime。

[6]　这里指的立方数从2的立方开始，因为1=13。

[7]　又称丰数或过剩数。

[8]　最近的例子是孪生素数猜想，传奇美籍华裔数学家张益唐在2013年取得重大进展，引起轰动。

[9]　又称埃氏筛或素数筛，简称筛法。埃拉托斯特尼（公元前276—公元前194），古希腊数学家、地理学家。

[10]　当解释有关任意数的性质的时候，数学家们会用符号为讨论的对象赋予名称。对于数，这些名字通常都是小写字母，如m和n；两个数的积m×n经常简写为mn。