Programmare in python: 1. Crivello di Eratostene

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.

Crivello di Eratostene Python

Crivello_di_Eratostene.py

2"""

3Crivello di Eratostene

5Descrizione:

6 Implementazione ricorsiva del crivello di Eratostene con decoratori.

7 Il decoratore `setup_crivello` gestisce la validazione dell'input

8 (da tastiera o da codice), calcola la lista dei numeri tramite

9 la funzione `crivello_core`, e gestisce il limite di ricorsione

10 e la visualizzazione grafica dei risultati tramite la funzione

11 opzionale `visualizza`.

13 Visualizzazione:

14 – Numeri primi in sfondo blu con testo bianco.

15 – Numeri non primi in sfondo bianco con testo nero.

16 – Stampa tabellare 10 x N.

20Autore: Alessio Severi

21Licenza: MIT License

23MIT License

27Permission is hereby granted, free of charge, to any person obtaining a copy

28of this software and associated documentation files (the "Software"), to deal

29in the Software without restriction, including without limitation the rights

30to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

31copies of the Software, and to permit persons to whom the Software is

32furnished to do so, subject to the following conditions:

34The above copyright notice and this permission notice shall be included in all

35copies or substantial portions of the Software.

37THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

38IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

39FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

40AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

41LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

42OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

43SOFTWARE.

45"""

48from typing import List

49from functools import wraps

50import sys

53def setup_crivello(n0, visual= None):

55 def decorator(funzione):

57 @wraps(funzione)

58 def wrapper(n: str | int) -> List[int]:

60 # Validazione del valore n

62 # Validazione da input

63 if isinstance(n, str):

64 if not n.isdecimal():

66 raise ValueError("Errore di input: inserire un valore intero")

68 n = int(n)

70 # In caso di immissione del valore direttamente da codice

71 # Conversione automatica per float

72 elif isinstance(n, float):

73 n = int(n)

75 # Tipi non numerici

76 elif not isinstance(n, int):

77 raise ValueError("Errore di valore: scrivere un valore intero")

79 # Controllo del valore minimo consentito

80 if n <= n0:

81 raise ValueError(f"Errore: il valore deve essere maggiore di {n0}")

84 # Limite ricorsivo

85 max_ri = sys.getrecursionlimit() – 1

87 if (n – n0 + 1) > max_ri:

88 raise RecursionError(f"n troppo grande per questa versione ricorsiva "

89 f"(max ≈ {n0 + max_ri – 1})")

92 # Creazione del setaccio

93 setaccio = list(range(n0, n + 1))

94 lista_primi = []

96 # Esecuzione del decoratore: calcola e opzionalmente visualizza i risultati

97 risultato= funzione(setaccio, lista_primi)

98 return visual(n, risultato) if visual is not None else risultato

100 return wrapper

101

102 return decorator

103

104

105

106# ———————————————–

107# Funzione principale del Crivello di Eratostene

108# ———————————————–

109def crivello_core(setaccio: List[int], lista_primi: List[int]) -> List[int]:

110 """

111 Implementazione ricorsiva del crivello di Eratostene.

112 Riceve il setaccio e la lista dei numeri primi trovati.

113 Rimuove i multipli del primo elemento del setaccio e prosegue

114 fino a svuotare il setaccio.

115 """

116

117 # Caso base: se il setaccio è vuoto → restituisce la lista dei primi

118 if not setaccio:

119 return lista_primi

120

121 # Primo numero del setaccio (nuovo divisore)

122 arg = setaccio[0]

123

124

125 # Funzione interna per filtrare i multipli dell'argomento corrente

126 def calcola(seta: List[int]) -> List[int]:

127

128 # Rotazione del setaccio: sposta l’ultimo elemento in testa

129 seta.insert(0, seta.pop())

130

131 # Se il ciclo ha completato una rotazione, restituisce il setaccio

132 if seta[0] == arg:

133 return seta

134

135

136 # Se il primo elemento è multiplo di arg, lo elimina

137 if seta[0] % arg == 0:

138 del seta[0]

139

140 # Ricorsione sulla nuova configurazione del setaccio

141 return calcola(seta)

142

143 # Applica la funzione di filtraggio e aggiorna la lista dei numeri primi

144 setaccio = calcola(setaccio)

145 lista_primi.append(setaccio[0])

146

147 # Chiamata ricorsiva sul nuovo setaccio

148 del setaccio[0]

149

150 return crivello_core(setaccio, lista_primi)

151

152

153# ——————————-

154# Funzione di visualizzazione

155# ——————————-

156def visualizza(n: int, lista_primi: list[int]):

157 """

158 Visualizzazione tabellare dei numeri da 2 a n.

159 Evidenzia i numeri primi in blu e i composti in bianco.

160 """

161

162 print("\n")

163 print(f"\033[47m\033[30m \033[0m", end="")

164

165

166 # Conversione in set per ottimizzare la ricerca (lookup O(1))

167 primi = set(lista_primi)

168

169 # Scansione dei numeri da 2 a n

170 for numero in range(2, n + 1):

171

172

173 # Numeri primi → blu (sfondo) con testo bianco

174 if numero in primi:

175

176 print(f"\033[44m {numero:4d} \033[0m", end="")

177

178 # Numeri non primi → sfondo bianco con testo nero

179 else:

180

181 print(f"\033[47m\033[30m {numero:4d} \033[0m", end="")

182

183 # A capo ogni 10 numeri

184 if numero % 10 == 0:

185

186 print()

187

188 # Riempimento per completare la tabella (10xN)

189 if resto:= n % 10:

190 for _ in "_" * (10 – resto):

191

192 print(f"\033[47m\033[30m \033[0m", end="")

193

194

195 print("\n\n")

196

197 # Ritorno della lista di numeri primi per ulteriore implementazione

198 return lista_primi

199

200

201

202# —————————————————

203# Funzione di alto livello del Crivello di Eratostene

204# —————————————————

205@setup_crivello(2, visualizza)

206def crivello(setaccio: List[int], lista_primi: List[int]) -> List[int]:

207 return crivello_core(setaccio, lista_primi)

208

209

210

211# Titolo

212print("\n\033[1;34m{:^60}\n".format("CRIVELLO DI ERATOSTENE"))

213

214# Test

215crivello(input("Inserire il valore di n: "))

216

217# Test con input da codice

218# Commenta la riga di codice precedente e decommenta la seguente

219# per testare con input da codice

220# crivello(100)

221

222# Colorazione di default

223print("\033[0m")

224

225