Crivello di Eratostene

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 il calcolo dei numeri primi da molti programmi per computer, per via della sua semplicità. Pur non essendo particolarmente rapido ed efficiente, infatti, è piuttosto semplice da implementare in un qualsiasi linguaggio di programmazione.

Algoritmo

 

Animazione del crivello

Il procedimento è il seguente: si scrivono tutti i numeri naturali a partire da ${\displaystyle 2}$  fino ${\displaystyle n}$  in un elenco, detto setaccio. In seguito si cancellano (setacciano) tutti i multipli del primo numero del setaccio escluso lui stesso. Si prende poi il primo numero non cancellato maggiore di ${\displaystyle 2}$  e si cancellano tutti i suoi multipli eccetto lui, e si ripete questa operazione fino a che il primo numero non cancellato maggiore di ${\displaystyle 2}$  non presenta multipli tra i numeri rimasti nell'elenco. I numeri che restano sono i numeri primi minori o uguali a ${\displaystyle n}$ .

È come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare solo i numeri non multipli di ${\displaystyle 2}$ , il secondo solo i non multipli di ${\displaystyle 3}$ , e così via.

Nel caso ${\displaystyle n=50}$ , ad esempio, il procedimento di setacciatura si conclude con il numero ${\displaystyle 7}$  perché ${\displaystyle 7}$  è il massimo numero primo il cui quadrato non supera ${\displaystyle 50}$ ; si può provare che il procedimento di setacciatura per ricercare i primi fino a un certo numero ${\displaystyle n}$  termina sempre quando si raggiunge la radice quadrata di ${\displaystyle n}$ . Ogni numero ${\displaystyle a}$  del setaccio iniziale, contenente tutti i numeri naturali non superiori a un dato ${\displaystyle n}$ , cade dal setaccio che corrisponde al più piccolo dei suoi divisori primi.

Se indichiamo con ${\displaystyle p}$  il più piccolo divisore primo di ${\displaystyle a}$  si ha:

${\displaystyle a=p\cdot r{\text{ con }}r\geq p.}$ 

Se ne deduce che ${\displaystyle a=p\cdot r\geq p\cdot p=p^{2}}$ , da cui ${\displaystyle p}$  è sempre minore o uguale alla radice quadrata di ${\displaystyle a}$ .

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 ${\displaystyle 30}$ , si può procedere come segue:

• Scrivere la lista di tutti i numeri interi da ${\displaystyle 2}$  a ${\displaystyle 30}$ :

  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 ${\displaystyle 2}$ :

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

• Il primo numero ancora presente nella lista dopo il ${\displaystyle 2}$  è il ${\displaystyle 3}$ ; cancellare dalla lista i rimanenti multipli di ${\displaystyle 3}$ :

  2  3     5     7          11    13          17    19          23    25          29

• Il primo numero ancora presente nella lista dopo il ${\displaystyle 3}$  è il ${\displaystyle 5}$ ; cancellare dalla lista i rimanenti multipli di ${\displaystyle 5}$ :

  2  3     5     7          11    13          17    19          23                29

• Il primo numero ancora presente nella lista dopo il ${\displaystyle 5}$  è il ${\displaystyle 7}$ : non essendoci più nessun multiplo di ${\displaystyle 7}$  nella lista, i numeri restanti sono i numeri primi cercati.

Altri progetti

Altri progetti

• Wikibooks
• Wikimedia Commons

•   Wikibooks contiene testi o manuali sul crivello di Eratostene
•   Wikimedia Commons contiene immagini o altri file sul crivello di Eratostene

Collegamenti esterni

• Eratostene, crivello di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.  
• (EN) sieve of Eratosthenes, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  
• (EN) Eric W. Weisstein, Sieve of Eratosthenes, su MathWorld, Wolfram Research.  
• (EN) Eratosthenes, sieve of, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.  

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica