五二小说网

手机浏览器扫描二维码访问

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

孪生素数对，即101，103和107，109。

素数在数千年来一直深深吸引着人们[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整除：