Considere um número inteiro positivo x. Como podemos encontrar todos os números primos que não excedem x? Existe um método chamado Crivo de Eratóstenes, cuja história remonta à Grécia Antiga. Os passos do Crivo de Eratóstenes são os seguintes: Primeiro, liste todos os números inteiros de 2 a x, mantendo 2 e eliminando todos os múltiplos de 2. Segundo, na lista restante, o próximo número primo após 2 é 3; mantenha 3 e elimine todos os múltiplos de 3. Terceiro, na lista restante, o próximo número primo após 3 é 5; mantenha 5 e elimine todos os múltiplos de 5. Assim, no último passo, na lista restante do passo anterior, mantenha o número primo mais próximo que não exceda x e elimine todos os seus múltiplos. A lista restante será então todos os números primos que não excedem x. Este método baseia-se no facto de que, se a não for um número primo, deve ter um fator que não exceda .
O Crivo de Eratóstenes pode ser usado para criar uma tabela de números primos de forma relativamente fácil. Se nos depararmos com um número inteiro positivo não muito grande (por exemplo, não superior a 10000) e não tivermos uma tabela de números primos disponível, como podemos determinar rapidamente se é um número primo? Na verdade, basta dividir o número a por todos os números primos que não excedam .