Il crivello di Eratostene è un antico algoritmo per il calcolo dei numeri primi fino a un certo numero prefissato. Deve il proprio nome al matematico greco antico Eratostene di Cirene, che ne fu l'ideatore. È ancora utilizzato per l'individuazione dei numeri primi da molti programmi per elaboratori elettronici, per via della sua semplicità. Pur non essendo particolarmente rapido ed efficiente, infatti, è piuttosto semplice da implementare in un qualsiasi linguaggio di programmazione.

Algoritmo

Il procedimento è il seguente.

Si predispone un elenco ordinato di tutti i numeri naturali a partire da fino ad e si cancellano dall'elenco tutti i multipli di escluso stesso. Si prende poi il primo numero non cancellato maggiore di e si cancellano tutti i suoi multipli eccetto lui stesso. In seguito si ripete questa operazione con i successivi numeri non cancellati maggiori di , in ordine crescente, fino a quando se ne trova uno che non presenta multipli tra i numeri rimasti nell'elenco. I numeri che restano nell'elenco sono i numeri primi minori o uguali a .

L'algoritmo prende il nome dal fatto che, applicandolo, si procede come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare solo i numeri non multipli di , il secondo solo i non multipli di , e così via.

Nel caso , ad esempio, il procedimento di setacciatura si conclude con il numero , che è il massimo numero primo il cui quadrato non supera ; si può provare che il procedimento di setacciatura per ricercare i primi fino a un certo numero termina sempre con il setaccio che corrisponde al più piccolo numero naturale minore della radice quadrata di . Ogni numero del setaccio iniziale, contenente tutti i numeri naturali non superiori a un dato , cade dal setaccio che corrisponde al più piccolo dei suoi divisori primi.

Se indichiamo con il più piccolo divisore primo di si ha:

Se ne deduce che , da cui è sempre minore o uguale alla radice quadrata di .

Una implementazione dell'algoritmo di Eratostene in Haskell che calcola l'n-esimo numero primo: -- Una lista infinita di numeri primi prodotta -- attraverso il metodo del crivello di Eratostene. crivello :: [Int] crivello = crivello' [2..] where crivello' :: [Int] -> [Int] crivello' (p:ps) = p : crivello' [i | i <- ps, mod i p /= 0] crivello' _ = undefined

-- Estrai il n-esimo numero primo. eratostene :: Int -> Int eratostene n = crivello !! n

Esempio

Per trovare tutti i numeri primi minori di , si può procedere come segue:

Scrivere la lista di tutti i numeri interi da a : 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Cancellare dalla lista i multipli di : 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Il primo numero ancora presente nella lista dopo il è il ; cancellare dalla lista i rimanenti multipli di : 2 3 5 7 11 13 17 19 23 25 29 Il primo numero ancora presente nella lista dopo il è il ; cancellare dalla lista i rimanenti multipli di : 2 3 5 7 11 13 17 19 23 29 Il primo numero ancora presente nella lista dopo il è il : non è più presente nessun multiplo di nella lista, pertanto i numeri restanti sono i numeri primi cercati. Il procedimento è terminato con il setaccio corrispondente ai multipli di , che è il più piccolo numero naturale inferiore alla radice quadrata di .

Altri progetti

Collegamenti esterni

Categoria:Algoritmi per la matematica Categoria:Scienza ellenistica Categoria:Numeri primi