Programmare in python: 1. Crivello di Eratostene
Introduzione
Il Crivello di Eratostene è uno degli algoritmi più antichi e ingegnosi nella storia della matematica, concepito per individuare tutti i numeri primi fino a un limite prefissato. L’algoritmo prende il nome dal matematico e astronomo greco Eratostene di Cirene (circa 276–194 a.C.), figura poliedrica del periodo ellenistico nota anche per la misurazione del raggio terrestre e per i suoi studi di geografia e cronologia.
Il metodo del crivello si basa su un principio di eliminazione progressiva: a partire dalla lista ordinata dei numeri naturali, vengono rimossi i multipli di ciascun numero primo identificato, lasciando infine soltanto i numeri primi. Tale procedura, tanto semplice quanto profonda, rappresenta un esempio di razionalità algoritmica ante litteram, anticipando di secoli l’idea moderna di efficienza computazionale.
Il Crivello di Eratostene non è solo un esercizio di aritmetica, ma anche una finestra sulla concezione greca dell’ordine numerico, in cui la scoperta dei numeri primi assumeva un valore quasi filosofico: individuare ciò che è indivisibile e perfetto. La sua eleganza concettuale ha reso l’algoritmo un punto di riferimento nella didattica e nella storia dell’informatica, nonché una delle basi su cui si sono sviluppati i moderni metodi di calcolo dei numeri primi.
Risultato
L’algoritmo del Crivello di Eratostene è stato qui implementato in forma ricorsiva, con due ricorsioni annidate, per evidenziare la natura induttiva del procedimento: ad ogni passo si seleziona un numero primo e si eliminano i suoi multipli, ripetendo il processo fino all’esaurimento del setaccio. Questa scelta ha un valore prevalentemente didattico e concettuale, mentre in applicazioni pratiche si preferisce una versione iterativa, più efficiente e priva dei limiti imposti dalla profondità di ricorsione del linguaggio.
La struttura ricorsiva permette tuttavia di visualizzare in modo chiaro la logica interna del crivello e di esplorarne la progressione in maniera più espressiva.
Link utili
▶ Esegui il programma su Replit:
1. Clicca sul link Apri su Replit per accedere al progetto.
2. Se non hai un account Replit, registrati gratuitamente oppure accedi con Google/GitHub.
3. Una volta nel progetto, premi “Run” per avviare l’esecuzione.
4. Puoi consultare il file sorgente e, se desideri, scaricarlo o copiarlo dal pannello di codice a sinistra.
▶ Scarica la versione portatile del codice:
1. Clicca sul link Scarica File per scaricare il file Crivello_di_Eratostene.txt, che contiene il codice sorgente completo in formato .txt.
2. Rinomina il file cambiando l’estensione da .txt a .py.
3. Ora puoi eseguirlo localmente su qualsiasi IDE per python (es. VS Code, IntelliJ IDEA, Eclipse con PyDev o NetBeans con plugin Python) oppure direttamente da terminale con il comando: python3 Crivello_di_Eratostene.py (oppure python Crivello_di_Eratostene.py su Windows, se Python 3 è impostato come interprete predefinito), eseguendo il file con l’interprete Python.
▶ Utilizzo:
Il parametro n rappresenta il limite superiore dell’intervallo [2, n] entro cui il programma calcola e visualizza i numeri primi. La scelta di n può essere adattata alle dimensioni del display o alla velocità di esecuzione desiderata.
Il programma gestisce automaticamente la formattazione in tabella e la visualizzazione dei risultati, distinguendo i numeri primi e i numeri non primi tramite colori e simboli grafici.
Codice
L’eleganza del crivello risiede nella sua semplicità concettuale e nella sua straordinaria efficienza. Nonostante le origini antiche, il principio logico alla base dell’algoritmo si presta perfettamente alle moderne implementazioni informatiche. La versione qui presentata, realizzata in Python, ne rielabora la struttura attraverso un approccio ricorsivo, offrendo una lettura contemporanea di un metodo che continua a rappresentare un fondamento nella teoria dei numeri.