Il crivello di Eratostene

Come si elencano tutti i numeri primi fino a un certo numero $N$? Eratostene di Cirene (III secolo a.C., bibliotecario di Alessandria) inventò un algoritmo elegante: il crivello (in greco koskinon, “setaccio”), che ancora oggi è il metodo più semplice per generare tabelle di numeri primi.

Esempio — Crivello di Eratostene fino a 30

Si scrivono i numeri da $2$ a $30$ e si procede così:

1. Si cerchia il primo numero non cancellato ($2$): è primo.
2. Si cancellano tutti i suoi multipli successivi ($4,6,8,\ldots,30$).
3. Si torna al passo 1 sul prossimo non cancellato ($3$), poi $5$, poi $7$.
4. Quando si arriva a un primo $p$ con $p^2>N$ (qui $p=7$, poiché $7^2=49>30$) ci si può fermare: tutti i restanti non cancellati sono primi.

Restano: $\boxed{2,3,5,7,11,13,17,19,23,29}$ — i $10$ primi fino a $30$.

Il crivello fino a 30: cerchiati in rosso i primi, in grigio i numeri cancellati perché composti.

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Crivello di eratostene · Numero primo
Metodi: Crivello eratostene
Competenze: Calcolare
Persone: Eratostene