Il Crivello di Eratostene

Home

 

 

Il Crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato. Deve il nome al matematico Eratostene di Cirene, che ne fu l'ideatore. È a tutt'oggi utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente efficiente.

 

Descrizione dell’algoritmo

 

L’algoritmo è di categoria forza bruta, prevede la scrittura di tutti i numeri naturali a partire da 1 fino a un certo n dato in ingresso in un elenco. Poi si cancellano tutti i multipli del primo numero (escluso lui stesso). Si prosegue così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n.

 

L’algoritmo è paragonabile a un setaccio a maglie via via più larghe: il primo lascia passare solo i multipli di 2, il secondo solo i multipli di 3, e così via. Nel caso n = 50, ad esempio, il procedimento di setacciatura si conclude con il numero 7 perché 7 è il massimo intero il cui quadrato non supera 50 e si può provare che il procedimento di  setacciatura per ricercare i primi fino ad un certo numero n cessa sempre quando si supera la radice quadrata di n.  

                   

File:Portrait of Eratosthenes.png

 

 

 

 

 

 

Eratostene di Cirene               

 

Home