Crivello di Eratostene

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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 ${\displaystyle 2}$ fino ${\displaystyle n}$ 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 ${\displaystyle 2}$ 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 ${\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 primo il cui quadrato non supera ${\displaystyle 50}$ e si può provare che il procedimento di setacciatura per ricercare i primi fino a un certo numero ${\displaystyle n}$ cessa sempre quando si supera la radice quadrata di ${\displaystyle n}$. Infatti 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 della lista dopo il ${\displaystyle 2}$ è il ${\displaystyle 3}$; cancellare dalla lista i multipli di ${\displaystyle 3}$:

  2  3     5     7          11    13          17    19          23    25          29

• Il primo numero della 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 della lista dopo il ${\displaystyle 5}$ è il ${\displaystyle 7}$: non essendoci più suoi multipli, i numeri restanti sono i numeri primi che cercavamo.

Altri progetti

• 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 Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
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

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