Prendiamo un numero intero positivo x. Come possiamo trovare tutti i numeri primi che non superano x? Esiste un metodo chiamato crivello di Eratostene, la cui storia risale all'antica Grecia. I passaggi del crivello di Eratostene sono i seguenti:
- Nella prima fase, elenchiamo tutti i numeri interi da 2 a x, mantenendo 2 e eliminando tutti i multipli di 2.
- Nella seconda fase, tra i numeri rimanenti, il primo numero primo successivo a 2 è 3; manteniamo 3 ed eliminiamo tutti i multipli di 3.
- Nella terza fase, tra i numeri rimanenti, il primo numero primo successivo a 3 è 5; manteniamo 5 ed eliminiamo tutti i multipli di 5.
- Continuando in questo modo, nell'ultima fase, tra i numeri rimanenti dell'ultima fase, manteniamo il numero primo più vicino a x e eliminiamo tutti i suoi multipli.
In questo modo, l'elenco rimanente sarà quello dei numeri primi che non superano x.
Questo metodo si basa sul fatto che, se a non è un numero primo, allora a deve avere un fattore che non supera .
Con il crivello di Eratostene, è possibile creare tabelle dei numeri primi in modo relativamente semplice. Se ci troviamo di fronte a un numero intero positivo non molto grande (ad esempio, non superiore a 10000) e non abbiamo a disposizione una tabella dei numeri primi, come possiamo determinare rapidamente se è un numero primo? In realtà, basta dividere a per tutti i numeri primi che non superano .