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