Con un po' di tempo libero a disposizione mi sono cimentato nell'implementazione del famoso Crivello di Eratostene, per la ricerca dei numeri primi, utilizzando il linguaggio Python.
Sono partito dall'algoritmo, sviluppato con GW-BASIC, presente in questo articolo https://www.sebcosta.altervista.org/joomla/articles/30-crivello-di-erastotene-in-gw-basic.html
Ecco qui il programma:
import math
def Eratostene(n):
# prepara il setaccio con una lista da a[1] a a[n] (a[0] viene ignorato)
# la lista viene creata con tutti valori a 0
a = [0] * (n+1)
max = int(math.sqrt(n)) # determina fine setacciatura
for i in range(2, max + 1):
j = i + i # i*2
while j <= n:
a[j] = 1 # marchia j come "non primo"
j = j + i # i*3,i*4,i*5,...
# crea lista in output
primi = []
for i in range(2, n + 1):
if a[i] == 0:
primi.append(i)
return primi
n=int(input("Inserisci N="))
primi = Eratostene(n)
print(primi)
Rispetto alla versione GW-BASIC, la versione Python è senz'altro molto più leggibile!
Alcune note:
- l'array per il "setaccio" viene implementato tramite una lista
- l'indice 0 della lista "setaccio" non viene utilizzato (in realtà, nella pratica, neanche l'indice 1 viene utilizzato)
- la fase di "setacciatura" avviene senza eseguire alcuna moltiplicazione, ma semplicemente eseguendo addizioni ripetute.
- la funzione Eratostene(n) ritorna una lista dei numeri primi trovati, quindi alla fine della funzione si scorre il setaccio per determinare i valori che non hanno divisori.
Ecco un esempio di esecuzione:
Inserisci N=100
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Sarebbe per me molto interessante riscrivere l'ultima parte, in cui si crea la lista di numeri primi, in un modo più pythonico: al momento non ho trovato alcuna alternativa... se qualcuno ha qualche suggerimento mi faccia sapere!!!
