Crea sito

Crivello di Eratostene

Crivello di Eratostene – Il crivello di Eratostene è un antico algoritmo per il calcolo delle tabelle di numeri primi fino a un certo numero n 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 2 fino 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  2 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  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 , 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 a 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 a 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:

Esempio

Per trovare tutti i numeri primi minori di 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, non essendoci più multipli i numeri restanti sono i numeri primi che cercavamo.

Animation Sieve of Eratosth

Animation Sieve of Eratosth

Il testo è disponibile secondo la licenza Creative Commons Da Wikipedia, l’enciclopedia libera.

Animation Sieve of Eratosth disponibile secondo la licenza Creative Commons Da Wikimedia Commons, l’archivio di file multimediali liberi

Leggi anche…

Numero fortunato – In teoria dei numeri, un numero fortunato è un numero naturale in un insieme generato da un “crivello” simile al crivello di Eratostene che genera numeri primi… [ Continua a leggere ]

Lascia il tuo commento:
CHIUDI
CHIUDI
shares
Visit Us On FacebookVisit Us On TwitterVisit Us On PinterestVisit Us On InstagramVisit Us On Youtube