天才一秒记住【狂风中文网】地址：https://www.kfzw.net
为了找出不大于某个数（比如100）的所有素数，最容易想到的方法是把所有数写下来，再寻找并画掉里面的合数。
基于这一思想的标准方法叫作埃拉托斯特尼筛法[9]（SieveofEratosthenes）。
方法如下：首先圈出2并画掉列表里2的倍数（即其他偶数）。
然后回到开始，圈出第一个尚未被画掉的数（即3），画掉剩下数表里它的所有倍数。
重复这一过程足够多遍，剩下没有被画掉的就是素数。
即便它们中一些被圈出来了，而另一些没有。
例如，图1展示了对不大于60的数运用筛法的过程。
图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=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倍，重复操作直到可判断整除性。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！