Un setaccio per i numeri primi: il Crivello di Eratostene

Ci siamo occupati a più riprese di Eratostene, che da brillante cartografo, riuscì nientemeno che a misurare la circonferenza della terra.

Eratostene si occupò anche di aritmetica e, naturalmente, di numeri primi ideando un criterio estremamente semplice per identificarli. Il criterio, oggi noto come Crivello di Eratostene, agisce esattamente come un setaccio, eliminando progressivamente numeri fino a restare con la serie dei numeri primi.

Abbiamo già parlato di numeri primi: sappiamo che un numero può essere primo o composto, cioé ottenuto per prodotto di numeri primi. Per determinare se un numero è primo o no, occorre tentare una serie di divisioni per tutti i numeri primi minori. Eratostene, invece, ha una intuizione per ridurre il numero di divisioni ed operare invece in modo inverso. Ma andiamo con ordine.

Supponendo di voler determinare i numeri primi tra 1 e 50:

 1     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

L’idea di Eratostene è di eliminare i numeri composti, progressivamente, fino a rimanere con tutti e soli i numeri primi.
Il primo passo del crivello è di eliminare, quindi, i multipli di 2:

 1    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

e, con ciò, si elimina già il 50% dei candidati. Notate come si eliminino i multipli di 2, ma non il 2 stesso, in quanto è numero primo.
Il secondo passo è quindi di eliminare tutti i multipli del secondo candidato a disposizione, cioé il 3:

 1    2     3          5
 7
 11         13
 17         19
 23                   25
 29
 31                   35
 37
 41         43
 47         49

sappiamo ora che i numeri rimasti non sono divisibili né per 2 né per 3. Continuiamo quindi ad eliminare i numeri multipli del prossimo candidato, cioé 5:

 1    2     3          5
 7
 11         13
 17         19
 23
 29
 31
 37
 41         43
 47         49

Infine, eliminiamo i candidati multipli del prossimo numero primo, il 7:

 1    2     3          5
 7
 11         13
 17         19
 23
 29
 31
 37
 41         43
 47

Il criterio termina quando arriviamo ad eliminare i multipli dell’ultimo numero il cui quadrato è inferiore al numero di candidati iniziali. Nel caso specifico, 7, perché 7×7 = 49.

Perché ci fermiamo al 7 e, soprattuto, perché il Crivello di Eratostene funziona ?

Lo vediamo la prossima volta.