Il Crivello di Eratostene è un algoritmo che permette di calcolare rapidamente i numeri primi che si trovano nell’intervallo (1 … N) con N grande a piacere.
Il metodo inventato da Eratostene consiste in una serie di passi da eseguire.
- 1 – Scrivere tutti i numeri da 1 fino al numero N scelto. Selezionare il numero 2.
- 2 – Eliminare dalla lista dei numeri tutti i multipli del numero correntemente selezionato.
- 3 – Nella lista dei numeri rimasti selezionare il numero successivo. Se il numero selezionato è superiore alla radice quadrata di N andare al passo 4 altrimenti ripetere il passo 2
- 4 – Il processo è terminato e quello che resta è la lista dei numeri primi da 1 a N.
Per esempio se vogliamo trovare tutti i numeri primi compresi tra 1 e 20 facciamo così:
Scriviamo la lista dei numeri da 1 a 20: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Eliminiamo tutti i multipli di 2. Rimangono i numeri 1 2 3 5 7 9 11 13 15 17 19
Il numero successivo è il 3. Eliminiamo tutti i multipli di 3. Rimangono i numeri 1 2 3 5 7 11 13 17 19
Il numero successivo è il 5 che è superiore alla radice quadrata di 20. Quindi il processo è terminato.
Vai alla pagina di implementazione dell’algoritmo di Eratostene