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. È ancora 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

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: $a = p \times r$ con $\,\!r > p$.

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

Esempio

Per trovare tutti i numeri primi minori o uguali a 30, si può procedere come segue:

• Scrivere la lista di tutti i numeri interi da 2 a 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 2:

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

• Il primo numero della lista dopo il 2 è il 3; cancellare dalla lista i multipli di 3:

  2  3     5     7          11    13          17    19          23    25          29

• Il primo numero della lista dopo il 3 è il 5; cancellare dalla lista i rimanenti multipli di 5:

  2  3     5     7          11    13          17    19          23                29

• Il primo numero della lista dopo il 5 è il 7, ma il quadrato di 7 è 49, che è maggiore di 30 quindi

il procedimento è terminato. La lista finale consiste di tutti i numeri primi inferiori o uguali a 30.

Altri progetti

• Wikiversità

• Wikiversità contiene informazioni su Il crivello di Eratostene(implementazione in C)

Collegamenti esterni

(EN) Eric W. Weisstein, Crivello di Eratostene su MathWorld.