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
| 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 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
- Partendo dal 2, cancelliamo tutti i multipli di 2 (escluso il 2).
| 2 | 3 | 5 | 7 | 9 | |||||
| 11 | 13 | 15 | 17 | 19 | |||||
| 21 | 23 | 25 | 27 | 29 | |||||
| 31 | 33 | 35 | 37 | 39 | |||||
| 41 | 43 | 45 | 47 | 49 | |||||
| 51 | 53 | 55 | 57 | 59 | |||||
| 61 | 63 | 65 | 67 | 69 | |||||
| 71 | 73 | 75 | 77 | 79 | |||||
| 81 | 83 | 85 | 87 | 89 | |||||
| 91 | 93 | 95 | 97 | 99 |
- Cancelliamo tutti i multipli di 3 (escluso il 3).
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 25 | 29 | |||||||
| 31 | 35 | ||||||||
| 41 | 43 | 47 | 49 | ||||||
| 53 | 55 | 59 | |||||||
| 61 | 65 | 67 | |||||||
| 71 | 73 | 77 | 79 | ||||||
| 83 | 85 | 89 | |||||||
| 91 | 95 | 97 |
- 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.
| 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 |
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.
