Crivello di Eratostene

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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: a = p \times r con \,\!r \ge 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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

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