取一個正整數 x，如何找出不超過 x 的所有質數呢？有一种方法叫做埃拉托色尼筛法，其历史可以追溯到古希腊时期。埃拉托色尼筛法的步骤如下：第一步，列出从 2 到 x 的所有整数，保留 2，划去所有 2 的倍数。第二步，在剩余的数列中，紧跟着 2 的质数是 3；保留 3，划去所有 3 的倍数。第三步，在剩余的数列中，紧跟着 3 的质数是 5；保留 5，划去所有 5 的倍数。如此下去，最后一步是在倒数第二步的剩余数列中，保留最接近且不超過 x 的那个质数，划去这个质数的所有倍数。这样，剩下的数列就是不超過 x 的所有質數。上述做法基于这样一个事实：如果 a 不是質數，那么 a 一定有不大於 的因子。
使用埃拉托色尼筛法可以比较方便地编制质数表。如果遇到一个不大的正整數 a（比如不超過 10000），而手头恰好没有质数表可查，如何快速判断它是否是质數呢？事实上，只需用不大於 的所有质數去除 a 即可。