Apri il menu principale

Crivello di Eratostene

algoritmo per trovare i numeri primi

Il crivello di Eratostene è un antico algoritmo per il calcolo delle tabelle di numeri primi fino a un certo numero prefissato. Questo principio deve il proprio nome al matematico Eratostene di Cirene, che ne fu l'ideatore. È ancora utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer, per via della sua semplicità pur non essendo del tutto efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio di programmazione.

AlgoritmoModifica

Il procedimento è il seguente: si scrivono tutti i numeri naturali a partire da   fino   in un elenco detto setaccio. Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui stesso). Si prende poi il primo numero non cancellato maggiore di   e si ripete l'operazione con i numeri che seguono, proseguendo fino a che non si applica l'operazione all'ultimo numero non cancellato. I numeri che restano sono i numeri primi minori o uguali a  .

È 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   perché   è il massimo primo il cui quadrato non supera   e si può provare che il procedimento di setacciatura per ricercare i primi fino a un certo numero   cessa sempre quando si supera la radice quadrata di  . Infatti 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:

takePrime :: Int -> Int
takePrime = takePrimeAux [2..]
  where
    takePrimeAux :: [Int] -> Int -> Int
    takePrimeAux (l:ls) 1 = l
    takePrimeAux (l:ls) n = takePrimeAux (filter (\x -> (mod x l) /= 0) ls) (n-1)

EsempioModifica

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 della lista dopo il   è il  ; cancellare dalla lista i multipli di  :
  2  3     5     7          11    13          17    19          23    25          29
  • Il primo numero della lista dopo il   è il  ; cancellare dalla lista i rimanenti multipli di  :
  2  3     5     7          11    13          17    19          23                29
  • Il primo numero della lista dopo il   è il  , non essendoci più multipli i numeri restanti sono i numeri primi che cercavamo.

Altri progettiModifica

Collegamenti esterniModifica

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