图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的素因数,我们需要多做一点工作。尽管如此,仍然有一些整除性测试方法,比计算完整的除法更快捷。