Cosa devi sapere sui numeri primi

Una tabella di numeri primi

Un antico metodo per trovare tutti i numeri primi inferiori a un dato numero prende il nome di crivello di Eratostene in onore al matematico e filosofo Eratostene (275-195 a.C.) che ne fu l'ideatore. L'idea consiste nell'eliminare tutti i numeri composti: i numeri rimanenti saranno primi. Il crivello può essere considerato un setaccio che lascia passare solo i numeri composti, trattenendo i numeri primi.

Vediamo come funziona supponendo di voler trovare tutti i numeri primi compresi tra 2 e 100. Scriviamo i numeri da 2 a 100 e tra questi eliminiamo i multipli di 2, eccetto 2. Tali numeri hanno infatti, oltre a 1 e se stessi, anche il 2 come divisore e quindi sono composti. Nella seguente tabella i numeri eliminati sono in grigio.

Eliminiamo poi tutti i multipli di 3, escluso il 3. A questo punto abbiamo anche eliminato tutti i multipli di 4, 6, 8, 9, 10 (perchè sono multipli di 2 o di 3). Eliminiamo infine i multipli di 5, escluso il 5 e i multipli di 7, escluso 7.

A questo punto tutti i numeri non cancellati sono primi perchè tutti i multipli di 11 minore di 100 sono già stati eliminati. Come si può osservare 11 è più grande della radice quadrata di 100 che è il numero più grande dell'intervallo considerato. Naturalmente il metodo si può generalizzare per determinare tutti i numeri primi compresi tra 2 e n. Prima dell'avvento delle calcolatrici meccaniche sono state compilate a mano tavole dei numeri primi fino a 100 milioni. Il crivello di Eratostene suggerisce un metodo per stabilire se un numero n è primo. Si divide n per ogni numero primo minore della radice quadrata di n. Se i resti delle divisioni sono tutti diversi da zero allora n è primo. Ad esempio, consideriamo il numero 97, i numeri primi minori della radice quadrata di 97 sono 2, 3, 5, 7 e siccome 97 non è divisibile per questi numeri possiamo affermare che è un numero primo. Questo metodo è detto divisione per tentativi ed è conveniente solo se il numero primo da testare è relativamente piccolo. Ad esempo, con questo metodo, se volessimo testare che 10.723 è un numero primo dovremmo eseguire ben 27 divisioni.