Crivello di Eratostene (circa 240 A.C.)

Supponiamo di voler trovare tutti i numeri primi minori o uguali ad N.

Si inzia scrivendo un elenco dei numeri da 2 ad N.

L'algoritmo procede come segue:

1. Si prende il numero più piccolo nella lista. Questo è un numero primo (all'inizio è 2, ed è ovvio che sia primo, ma come vedremo la regola continua a valere anche alle successive iterazioni) e fa parte della soluzione.

2. Si cancella il numero primo trovato e tutti i suoi multipli.

   Se il numero trovato è minore della radice quadrata di N, si torna al passo 1)

   altrimenti

   L'algoritmo è terminato. I numeri primi sono tutti quelli trovati, più quelli che rimangono non cancellati nella lista.