Crivello di Eratostene
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.
Algoritmo
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 per il quale c'è ancora almeno un suo multiplo. 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:
-- 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 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ù suoi multipli, i numeri restanti sono i numeri primi che cercavamo.
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, Crivello di Eratostene, su MathWorld, Wolfram Research.
- (EN) Crivello di Eratostene, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
V · D · M | ||
---|---|---|
Numeri più usati | Naturali · Interi · Pari e dispari | |
Principi generali | Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza | |
Successioni di interi | Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse | |
Caratteristiche dei numeri primi | Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi | |
Funzioni aritmetiche | Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens | |
Aritmetica modulare | Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica | |
Congetture | Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann | |
Altro | Problema di Waring | |
Principali teorici | Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet | |
Discipline connesse | Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri |