In questa lezione ti spiegherò uno dei metodi più antichi ed efficienti per il calcolo dei numeri primi: il crivello di Eratostene .
Il crivello di Eratostene
Si racconta che un giorno Eratostene andò da Tolomeo portando con se una lastra metallica, sulla quale erano incisi tutti i numeri naturali fino a 100. Ogni numero composto era stato cancellato con un forellino, per cui la tavola sembrava un crivello, cioè quello strumento utilizzato per setacciare la sabbia.
L’idea di Eratostene era molto semplice: eliminare in sequenza i numeri composti, in modo che sulla tavola rimanessero solo i numeri primi. Ti ricordo che un numero composto è un numero che non è primo.
Ti mostrerò con un esempio come calcolare i numeri primi da 1 a 100 usando il crivello di Eratostene.
Procedura da seguire:
1) La prima cosa da fare è scrivere in un elenco, o tabella, tutti i numeri naturali da 2 a 100.
2) Si comincia con il numero 2, che è un numero primo. Si cancellano tutti i numeri divisibili per 2, cioè tutti i numeri pari.
3) Il primo numero successivo al 2, tra quelli non cancellati, è il 3, che sarà quindi un altro numero primo. Si cancellano tutti i suoi multipli, cioè tutti i numeri divisibili per 3.
4) Il primo numero successivo al 3, tra quelli non cancellati, è il 5, che sarà quindi un altro numero primo. Si procede, ancora una volta, cancellando tutti i numeri divisibili per 5.
5) Il primo numero successivo al 5, tra quelli non cancellati, è il 7, che sarà quindi un altro numero primo. Si procede cancellando tutti i numeri divisibili per 7.
6) Tutti i numeri che restano sono stati cerchiati in rosso e sono i numeri primi da 1 a 100.
A questo punto ci si potrebbe chiedere, perché la procedura si è fermata quando siamo arrivati a 7?
La risposta è molto semplice. Il crivello di Eratostene permette di trovare tutti i primi minori di un certo numero, che indichiamo con X (nel nostro caso X = 100). Si può dimostrare che l’ultimo numero primo da considerare non deve superare la radice quadrata di X.
Nel nostro caso X = 100, quindi la sua radice quadrata è 10. Poiché 7 è l’ultimo numero primo minore o uguale a 10, possiamo fermarci. Se provassimo a continuare la procedura con numeri primi maggiori di 7, ci renderemmo conto che i loro multipli sono stati già cancellati. Pertanto, non c’è motivo di continuare, sarebbe solo uno spreco di tempo.