Crivello di Eratostene per trovare i numeri primi

Il Crivello di Eratostene è un antico procedimento per il calcolo delle tabelle dei numeri primi fino a un certo numero n prefissato. Deve il suo nome a Eratostene di Cirene (275-195 a.C.), grande matematico e astronomo greco dell’antichità.

Il crivello di Eratostene: come funziona

Esaminiamo il crivello di Eratostene per trovare tutti i numeri primi compresi, ad esempio, fra 1 e 100.

  • Scriviamo tutti i numeri compresi fra 2 e 100
2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • Partendo dal 2, cancelliamo tutti i multipli di 2 (escluso il 2).
2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • Cancelliamo tutti i multipli di 3 (escluso il 3).
2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • Continuiamo cancellando tutti i multipli del primo numero non ancora cancellato, escluso il numero stesso (5, 7, …), fino a non trovare più multipli da cancellare.
2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100

 

I numeri non cancellati sono tutti i numeri primi compresi, nel nostro caso, fra 1 e 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.