Stasera solito allenamento ma insolita, almeno per una palestra l’argomento del giorno: “Il crivello di eratostene”
Perchè le nostri strane menti sono arrivate a parlare di questo algoritmo , beh per due strani collegamenti : il primo è dato dal fatto che Eratostene, personaggio poliedrico che spaziava dalla matematica alla poesia che visse ad Alessandria d’Egitto città dei miei avi e il secondo perchè un po’ di matematica dei numeri primi non guasta mai 😛
A memoria credo sia il primo algoritmo utilizzato per calcolare i numeri primi sino a un n prefissato, ma tutt’oggi è utilizzano in molti calcolatori perchè se è pur vero che non è il più efficiente è il più semplice da implementare in qualsiasi linguaggio di programmazione, quindi spesso usato nelle introduzioni alla programmazione.
ALGORITMO
Prendiamo un foglio di carta e scriviamo tutti i naturali a partire da 2 fino n in un elenco, iniziamo a cancellare tutti i multipli del primo numero escluso lui stesso.
Proseguiamo così fino ad arrivare in fondo all’elenco. I numeri che restano sono i numeri primi minori od uguali a n.
ESEMPIO
Troviamo tutti i numeri primi sino a n=15
2 3 4 5 6 7 8 9 10 11 12 13 14 15
Cancelliamo tutti i numeri multipli di 2 (tranne se stesso)
2 3 5 7 9 11 13 15
Ora prendiamo il primo numero successivo al 2, quindi il 3 e cancelliamo tutti i suoi multipli
2 3 5 7 11 13
Il numero successivo è 5 i cui multipli non sono più in lista, stesso discorso per il 7.
Quindi i numeri restanti [ 2,3,5,7,11,13 ] sono i numeri primi inferiori o uguali a n=15
IMPLEMENTAZIONE
Python
def crivello_di_eratostene(n):
c=range(3, n+1, 2)
i=0
while c[i]<(n+1)**0.5:
j=i+1
while j<len(c):
if c[j] % c[i] == 0: del c[j]
j+=1
i+=1
return [2]+c