Il Crivello di Eratostene è un algoritmo ingegnoso utilizzato per trovare numeri primi fino a qualsiasi limite desiderato.
Questo metodo prende il nome dal matematico greco Eratostene di Cirene, vissuto nel III secolo a.C., a cui viene attribuita la prima descrizione dell’algoritmo.
In questo articolo guida scopriremo in cosa consiste il Crivello di Eratostene, come funziona nel dettaglio e quali sono le sue applicazioni per trovare numeri primi e per altri scopi didattici e ricreativi.
Vedremo anche alcuni esempi pratici di implementazione e la storia affascinante di questo importante algoritmo sviluppato nell’antica Grecia.
Cos’è il Crivello di Eratostene
Il Crivello di Eratostene è un procedimento che permette di trovare tutti i numeri primi minori di un numero naturale prefissato.
Questo risultato si ottiene partendo dall’elenco dei numeri naturali da 2 fino al limite considerato e cribrando via in sequenza i multipli di ogni numero primo trovato.
Crivellare ha il significato di setacciare, vagliare, ossia separare gli elementi grezzi da quelli raffinati o utili.
L’analogia visuale è quella di un setaccio che lascia passare solo i numeri primi, trattenendo i multipli.
I passaggi dell’algoritmo sono semplici ma efficaci:
- Si considera l’insieme dei numeri naturali da 2 al numero limite stabilito
- Si cancellano tutti i multipli di 2 diversi da 2 stesso
- Si considera il numero successivo non cancellato, in questo caso 3, e si cancellano tutti i suoi multipli
- Si procede analogamente con i successivi numeri non cancellati fino alla radice quadrata del limite prefissato
- I numeri non cancellati rappresentano proprio i numeri primi cercati
Vediamo quindi che il Crivello sfrutta un principio semplice ma potente: un numero è primo se e solo se non ha divisori propri tranne 1 e se stesso.
Trovando e cancellando sequenzialmente i multipli di ogni primo, rimangono solo i numeri primi fino al limite voluto.
Crivello di Eratostene online
Usa il crivello di Eratostene digitale per scomporre in fattori primi qualsiasi numero.
Come funziona il Crivello di Eratostene
Per comprendere più nel dettaglio il funzionamento del Crivello di Eratostene, analizziamo il procedimento passo passo:
1. Scrivi i numeri naturali da 2 al limite
Il primo passo è elencare i numeri naturali a partire da 2 fino al limite massimo desiderato. Ad esempio, per trovare i numeri primi minori di 100, si scrivono i numeri da 2 a 100.
2. Trova il primo numero primo dell’elenco
Il primissimo numero dell’elenco è certamente primo, ovvero il 2. Questo è il primo numero che useremo per crivellare, cancellando i suoi multipli.
3. Elimina i multipli
Si cancellano quindi tutti i multipli di 2 diversi dal 2 stesso. In questo caso vengono cancellati tutti i numeri pari successivi: 4, 6, 8, 10, 12 e così via. Rimangono solo i numeri non divisibili per 2.
4. Trova il numero primo successivo
A questo punto si considera il numero non cancellato successivo al 2, ossia il 3. Anche questo è certamente un numero primo.
5. Elimina i multipli del nuovo numero primo
Si cancellano quindi i multipli di 3, ossia 6, 9, 12, 15, 18 e così via. Già al passo precedente erano stati eliminati i multipli di 2, quindi ora vengono cancellati solo i multipli di 3 non eliminati precedentemente.
6. Ripeti dal passo 4
Si procede iterativamente considerando a turno i vari numeri rimasti e cancellando i loro multipli fino a quando non si arriva alla radice quadrata del limite stabilito.
Ad esempio, per i numeri minori di 100, l’ultimo multiplo da considerare è quello di 10, radice quadrata di 100. Dopo aver crivellato con i multipli di 2, 3, 5 e 7, possiamo fermarci, poiché tutti i compositi sono stati eliminati.
7. I numeri rimasti sono primi
Terminato il procedimento, i numeri che rimangono sull’elenco originale sono proprio tutti i numeri primi minori del limite fissato. Questi possono essere letti direttamente come output dell’algoritmo.
Esempi pratici del Crivello
Per consolidare la comprensione del Crivello di Eratostene, vediamo un paio di esempi pratici passo passo:
Esempio 1: numeri primi minori di 20
- Scriviamo i numeri da 2 a 20: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
- Il primo numero primo è 2.
- Cancello i multipli di 2: 4, 6, 8, 10, 12, 14, 16, 18, 20
- Il numero primo successivo è 3.
- Cancello i multipli di 3: 6, 9, 12, 15, 18
- Il prossimo numero primo è 5.
- Cancello i multipli di 5: 10, 15, 20
| Numero | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Cancella multipli di 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| Cancella multipli di 3 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| Cancella multipli di 5 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
I numeri rimasti, ovvero i primi minori di 20, sono: 2, 3, 5, 7, 11, 13, 17, 19.
Esempio 2: numeri primi minori di 30
Ripetiamo l’algoritmo per i numeri minori di 30:
- Scriviamo i numeri da 2 a 30
- Il primo numero primo è 2
- Cancello i multipli di 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28
- Il prossimo primo è 3
- Cancello i multipli di 3: 6, 9, 12, 15, 18, 21, 24, 27
- Il prossimo primo è 5
- Cancello i multipli di 5: 10, 15, 20, 25
I numeri primi minori di 30 sono: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Con pochi passaggi abbiamo ottenuto tutti i primi entro i limiti prefissati. L’algoritmo può essere applicato per qualsiasi limite desiderato, con complessità computazionale efficiente.
Implementazione del Crivello
L’algoritmo del Crivello di Eratostene può essere implementato efficacemente sia con carta e penna sia come programma software.
Vediamo alcuni modi per realizzare il Crivello:
- Su carta: basta disegnare una griglia con i numeri in colonna e cancellare manualmente i multipli via via trovati
- In un foglio elettronico: i numeri possono essere elencati in una colonna e poi formattati per barrarli quando identificati come compositi
- In linguaggi di programmazione: l’algoritmo può essere codificato in qualsiasi linguaggio come C, Python, Java, JavaScript e così via
- Su lavagna interattiva multimediale (LIM): gli studenti possono divertirsi a implementare il Crivello cancellando i numeri sulla lavagna elettronica
Il codice per implementare il Crivello richiede semplicemente un ciclo per scorrere i numeri e operazioni aritmetiche per trovare i multipli da eliminare. La struttura dati principale è un array booleano per contrassegnare i numeri primi o compositi.
L’implementazione più efficiente prevede di crivellare solo fino alla radice quadrata del limite, sfruttando il fatto che tutti i composti hanno almeno un divisore tra 2 e tale radice.
Applicazioni del Crivello di Eratostene
Il Crivello di Eratostene ha svariate applicazioni interessanti:
- Trovare numeri primi fino a un limite stabilito, anche molto grande
- Comprendere la distribuzione dei primi e la loro diminuzione all’aumentare del limite
- Stimare la funzione numero primo che conta i primi minori di un dato limite
- Verificare la primalità di un numero controllando se rimane dopo la crivellazione
- Fattorizzare numeri trovando divisori primi con il Crivello
- Generare chiavi crittografiche basate su numeri primi di grandi dimensioni
- Creare giochi ed esercizi didattici per apprendere i numeri primi
- Visualizzare graficamente la distribuzione dei primi con rappresentazioni del Crivello
È quindi uno strumento prezioso che con semplicità ed efficienza permette di esplorare a fondo la teoria dei numeri e le proprietà dei primi.
Storia del Crivello di Eratostene
La prima descrizione nota del procedimento risale al matematico greco Eratostene di Cirene (276 a.C. – 194 a.C.). Egli ricoprì l’importante ruolo di bibliotecario capo della Biblioteca di Alessandria, centro nevralgico della cultura ellenistica.
Eratostene contribuì significativamente allo sviluppo della matematica, dell’astronomia e della geografia.Tra le sue opere principali vi è un trattato Sulle medie, in cui formalizzò il concetto e il calcolo della media aritmetica.
Il Crivello di Eratostene viene descritto nelle sue opere come un metodo ingegnoso per trovare i numeri primi in modo efficiente. L’algoritmo rappresenta una delle prime applicazioni note del principio di inclusione ed esclusione.
Dopo Eratostene, il Crivello è stato riscoperto e impiegato da molti altri matematici nei secoli successivi, come Nicomaco di Gerasa e Pappos di Alessandria. Anche il grande matematico italiano Leonardo Fibonacci descrisse l’algoritmo nel XIII secolo.
Oggi il Crivello porta giustamente il nome del suo ideatore Eratostene ed è riconosciuto come uno degli algoritmi più antichi e geniali nella storia della matematica, oltre che tuttora molto utile e versatile.