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

Animazione del crivello


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 non cancellato. 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 ad 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 ad 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 .

Esempio[modifica | modifica wikitesto]

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ù multipli i numeri restanti sono i numeri primi che cercavamo.
    Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica