01 如何不去考虑数（第2页）
检测能否被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=27916924→2791684→279160
→27916→2779→259→7。
因此n可以被7整除。每执行一次指令循环，我们都至少能减少一位数，因此执行循环的次数大约与初始数的长度相同。
为了检测n是否有因数11，将原数的最后一位移除，再从新数中减去原数的最后一位，依此重复。比如，我们的方法揭示了下面这个数是11的倍数：
4959746→495968→49588
→4950→495→44=4×11。
检测能否被13整除，将原数最后一位移除，再用新数加上原数最后一位的4倍，接着用类似于7和11的方法，不断重复。比如，13是下面这个数的一个素因数：
11264331→1126437→112671
→11271→1131→117→39=3×13。
接下来是17和19。对于17，我们将原数最后一位移除，再用新数减去原数最后一位的5倍，重复操作直到可判断整除性；对于19，我们将原数最后一位移除，再用新数加上原数最后一位的2倍，重复操作直到可判断整除性。例如，我们来检测18905是否能被17整除：
18905→1865→161→11，
因而它不是17的倍数。但对于19，整除性测试给出了另一种结论：
18905→1900=100×19。
拥有了这一组测试，你现在就可以检查不大于500的所有数的素性，因为232=529超过了500，因此19是你需要考虑的最大的素因数。例如，为了确定247的性质，我们只需要检查它是否能被不大于13的素因数整除，因为下一个素数的平方，172=289超过了247。通过对13的测试，我们发现247→（24＋28）=52→13，这是一个13的倍数（247=19×13）。
素数相乘可以得到无平方因数的数（square-freenumber），要想构造关于这些数的整除性测试，可以叠加并行其素数因子的整除性测试。比如，对于42=2×3×7，一个数n能被42整除，当且仅当n可以通过2，3和7的三项整除性测试。但是，对于那些有平方数因数的数，像9=32，则不能由此得到。顺便说一句，9是n的因数，当且仅当9也是n的各位数字之和的因数。
你也许会问：数千年以来，那些聪明的数学家们难道还没有想出更好、更精妙的检测素性的方法？答案是有的。2002年，我们发现了一个相对快速的判断一个给定的数是否为素数的方法。不过，如果给定的数恰好是一个合数，那么这个所谓的“AKS素性测试”（AKSprimalitytest）并不能给出该数的因数分解。虽然原则上说找到一个给定数的素因数的问题可以通过试错来解决，但实际操作中，这对于很大的整数依然难以实现。正因为此，它构成了很多互联网加密方法的基础。我们会在第4章回到这个话题。在那之前，我们会在接下来的两章中更近距离地认识一下素数和因数分解。
[1] 这里用中文数字“六”，强调的是“六”这个数本身的概念，下同。—译者注。如无特殊说明，以下注释均为译者注。
[2] 我国的自然数包含0，而本书所说的自然数不包含0。
[3] 1码=3英尺=36英寸。
[4] 或称因子、约数，英文也可以写作divisor。
[5] 英文也可以写作prime。
[6] 这里指的立方数从2的立方开始，因为1=13。
[7] 又称丰数或过剩数。
[8] 最近的例子是孪生素数猜想，传奇美籍华裔数学家张益唐在2013年取得重大进展，引起轰动。
[9] 又称埃氏筛或素数筛，简称筛法。埃拉托斯特尼（公元前276——公元前194），古希腊数学家、地理学家。
[10] 当解释有关任意数的性质的时候，数学家们会用符号为讨论的对象赋予名称。对于数，这些名字通常都是小写字母，如m和n；两个数的积m×n经常简写为mn。——作者注