Il Crivello di Eratostene

Il crivello di Eratostene è uno degli algoritmi più antichi e conosciuti per la determinazione dei numeri primi. Ideato dal matematico greco Eratostene di Cirene nel III secolo a.C., questo metodo semplice ma efficace permette di identificare tutti i numeri primi fino a un determinato limite. La sua importanza risiede non solo nella sua semplicità, ma anche nella sua efficienza, che lo rende ancora oggi un argomento di studio e applicazione in vari campi della matematica e dell'informatica.

Questo articolo esplora il funzionamento del crivello di Eratostene, illustrandone i passaggi fondamentali attraverso un esempio pratico. Viene mostrato come, partendo da una lista di numeri naturali, sia possibile eliminare progressivamente i numeri composti per isolare i numeri primi.

Il crivello di Eratostene

In matematica, ed in particolare nella Teoria dei Numeri, un crivello, o setaccio, è un metodo per trovare tutti i numeri primi fino ad un certo valore massimo.

Abbiamo visto, infatti, che non esiste, almeno per quanto ne sappiamo, una formula che ci permetta di trovare l'ennesimo numero primo. E non conosciamo nemmeno una formula che ci dica come essi siano distribuiti tra i numeri naturali, per cui sembra che essi siano distribuiti in modo casuale. Questo è un argomento molto complesso e attualmente oggetto di ricerche matematiche.

Tuttavia, esistono metodi per trovare i numeri primi uno ad uno setacciando i numeri naturali, da cui il nome del metodo.

Ne esistono diversi di crivelli, ma il più antico e famoso è il crivello di Eratostene che prende il nome dal matematico greco Eratostene di Cirene (III secolo a.C.).

Esempio

Per capire come funziona il procedimento, proviamo a cercare tutti i numeri primi fino a 120.

Per prima cosa scriviamo in una tabella, in ordine, tutti i numeri naturali da 1 a 120.

**Figura 1:** Crivello di Eratostene - Tabella Iniziale

Non importa il numero di righe o di colonne, l'importante è che siano scritti tutti i numeri da 1 a 120 in sequenza.

La prima cosa da fare è rimuovere il numero 1, che non è primo:

**Figura 2:** Crivello di Eratostene - Rimozione di 1

A questo punto si prende il numero più piccolo rimasto, che è 2. Tale numero è sicuramente primo, quindi lo aggiungiamo alla lista dei numeri primi trovati.

**Figura 3:** Crivello di Eratostene - Partenza dal 2

La lista di numeri primi trovati finora è quindi: $2$ .

A questo punto scorriamo la lista dei numeri rimanenti e eliminiamo tutti i multipli di 2.

Il numero 3 non è multiplo di 2, quindi lo lasciamo. Il numero successivo è 4, che è multiplo di 2, quindi lo eliminiamo:

**Figura 4:** Crivello di Eratostene - Cancellazione 4

Andando avanti incontriamo il numero 5, che non è multiplo di 2, quindi lo lasciamo. Il numero successivo è 6, che è multiplo di 2, quindi lo eliminiamo:

**Figura 5:** Crivello di Eratostene - Cancellazione 6

Proseguiamo così, scorrendo il resto della lista e cancellando i multipli di 2. I multipli di 2 saranno per forza numeri composti, quindi non possono essere primi.

Questo è il risultato dopo aver cancellato tutti i multipli di 2:

**Figura 6:** Crivello di Eratostene - Cancellazione Multipli di 2

La nuova tabella che otteniamo è:

**Figura 7:** Crivello di Eratostene - Nuova Tabella dopo la rimozione dei multipli di 2

Adesso passiamo al numero immediatamente successivo al 2 che non è stato cancellato, ossia il numero 3.

Questo numero è sicuramente primo, quindi lo aggiungiamo alla lista dei numeri primi trovati: $2, \, 3$ .

**Figura 8:** Crivello di Eratostene - Partenza dal 3

Partendo dal 3 e scorrendo tutti i numeri rimasti successivi ad esso, eliminiamo tutti i multipli di 3 che non sono già stati cancellati. Tali numeri saranno sicuramente composti, quindi non possono essere primi:

**Figura 9:** Crivello di Eratostene - Cancellazione Multipli di 3

Il risultato è:

**Figura 10:** Crivello di Eratostene - Nuova Tabella dopo la rimozione dei multipli di 3

Il numero successivo al 3 che non è stato cancellato è il 5. Anche in questo caso si tratta di un numero primo, quindi lo aggiungiamo alla lista dei numeri primi trovati: $2, \, 3, \, 5$ .

Scegliamo il 5 come nuovo punto di partenza e cancelliamo tutti i suoi multipli:

**Figura 11:** Crivello di Eratostene - Cancellazione Multipli di 5

Il risultato è:

**Figura 12:** Crivello di Eratostene - Nuova Tabella dopo la rimozione dei multipli di 5

Il prossimo numero da considerare è il 7. Esso è primo e va aggiunto alla lista costruita finora: $2, \, 3, \, 5, \, 7$ .

Lo usiamo come nuovo punto di partenza e cancelliamo tutti i suoi multipli come fatto precedentemente.

I suoi multipli, rimasti in tabella, sono: $49$ , $77$ , $91$ e $119$ .

Il risultato sarà:

**Figura 13:** Crivello di Eratostene - Nuova Tabella dopo la rimozione dei multipli di 7

Arrivati a questo punto è inutile proseguire. Infatti il crivello di Eratostene si arresta quando raggiungiamo la radice quadrata del numero massimo che vogliamo considerare. Nel nostro caso la radice quadrata di 120 è circa 10.9:

\sqrt{120} \approx 10.9

Il numero successivo al 7 sarebbe 11 che, tuttavia, è maggiore di 10.9.

I numeri rimanenti nella tabella rappresentano tutti i numeri primi minori o uguali di 120:

\begin{array}{ccccc} 2 &amp; 3 &amp; 5 &amp; 7 &amp; 11 \\ 13 &amp; 17 &amp; 19 &amp; 23 &amp; 29 \\ 31 &amp; 37 &amp; 41 &amp; 43 &amp; 47 \\ 53 &amp; 59 &amp; 61 &amp; 67 &amp; 71 \\ 73 &amp; 79 &amp; 83 &amp; 89 &amp; 97 \\ 101 &amp; 103 &amp; 107 &amp; 109 &amp; 113 \end{array}

Quindi:

Definizione

Criterio di arresto del crivello di Eratostene

Il crivello di Eratostene si arresta quando si raggiunge la radice quadrata del numero massimo che si vuole considerare.

Se si vogliono trovare tutti i numeri primi fino a $n$ , si può arrestare il crivello quando si raggiunge $\sqrt{n}$ .

Il fatto che ci si possa fermare a $\sqrt{n}$ è dovuto al fatto che, se un numero $n$ non è primo, allora deve avere almeno un divisore minore o uguale a $\sqrt{n}$ . Nel procedimento allora tutti i multipli di tale divisore saranno stati già eliminati.

Ricapitoliamo, adesso, il procedimento per trovare tutti i numeri primi fino a $n$ con il crivello di Eratostene:

Definizione

Procedimento del crivello di Eratostene

Scrivere tutti i numeri naturali da 1 a $n$ in una tabella.
Eliminare il numero 1.
Prendere il numero più piccolo rimasto, che è sicuramente primo, e aggiungerlo alla lista dei numeri primi trovati.
Eliminare tutti i multipli di tale numero.
Ripetere i passaggi 3 e 4 fino a quando si raggiunge il massimo numero minore di $\sqrt{n}$ .

Una possibile implementazione in pseudo-codice del crivello di Eratostene è riportata nella figura che segue:

**Figura 14:** Crivello di Eratostene implementato in Pseudo-codice

Dove:

${{\rm R{\small IMUOVI}\;M{\small ULTIPLI}}}(tabella, primo)$ rimuove tutti i multipli di $primo$ dalla tabella.
${{\rm A{\small GGIUNGI}}}(primi, primo)$ aggiunge il numero $primo$ alla lista dei numeri primi trovati.

In particolare, la funzione ${{\rm R{\small IMUOVI}\;M{\small ULTIPLI}}}(tabella, primo)$ può essere implementata in pseudo-codice come mostrato nella prossima figura:

**Figura 15:** Funzione RIMUOVI MULTIPLI in pseudo-codice

Nel codice, la $tabella$ è rappresentata come un array di booleani, ossia di valori che possono essere $\mathbf{vero}$ o $\mathbf{falso}$ . Inizialmente tutti i valori sono impostati a $\mathbf{vero}$ , tranne il primo che rappresenta il numero 1, che è impostato a $\mathbf{falso}$ .

Successivamente, si scorrono tutti i numeri da $primo$ a $\sqrt{n}$ e si impostano a $\mathbf{falso}$ tutti i multipli di ciascun numero. Alla fine, i valori rimasti a $\mathbf{vero}$ rappresentano i numeri primi.

Sul sito è anche descritta un'implementazione del crivello di Eratostene per la calcolatrice TI-84 Plus:

Crivello di Eratostene per TI-84 Plus

In Sintesi

Nella Teoria dei Numeri non esiste, o almeno non è ancora stata trovata, una formula che ci permetta di trovare l'ennesimo numero primo. Tuttavia, esistono metodi per trovarli uno ad uno.

Tali metodi prendono il nome di crivelli o setacci proprio perché si basano su un procedimento di setacciatura dei numeri naturali.

Il più antico e famoso crivello è il crivello di Eratostene. Attraverso di esso possiamo trovare tutti i numeri primi fino ad un certo valore massimo $n$ .

In questa lezione abbiamo analizzato come esso funzioni e abbiamo visto un esempio pratico di come si possa trovare tutti i numeri primi fino a 120.

Nella prossima lezione vedremo come qualunque numero composto possa essere scomposto in fattori primi.

Lezione Precedente Indice del capitolo Lezione Successiva

Il Crivello di Eratostene