Crivello di Eratostene

Il crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato. Deve il nome al matematico Eratostene di Cirene, che ne fu l'ideatore. È a tutt'oggi utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio di programmazione.

Diverse generalizzazioni di questo metodo hanno dato vita alla teoria dei crivelli; tra di essi vi sono il crivello di Legendre e il crivello di Atkin.

Algoritmo

 

Animazione del crivello

Il procedimento è il seguente: si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio (in programmazione spesso l'elenco è implementato da un array). Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui stesso). Si prosegue così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n.

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

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

Se indichiamo con p il più piccolo divisore primo di a si ha: ${\displaystyle a=p\times r}$  con ${\displaystyle \,\!r>p}$ .

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

Altri progetti

Altri progetti

• Wikibooks
• Wikiversità
• Wikimedia Commons

•   Wikibooks contiene testi o manuali sul Il crivello di Eratostene(implementazione in C)
•   Wikiversità contiene risorse su Il crivello di Eratostene(implementazione in C)
•   Wikimedia Commons contiene immagini o altri file su Il crivello di Eratostene(implementazione in C)

Collegamenti esterni

(EN) Eric W. Weisstein, Crivello di Eratostene, in MathWorld, Wolfram Research.