Il crivello di Eratostene.

Il crivello di Eratostene.

 

Il crivello di Eratostene è un metodo per determinare i numeri primi noto fin dall’antichità. Per determinare tutti i numeri primi positivi non maggiori di n è sufficiente cancellare tutti i numeri composti che sono multipli dei numeri primi non maggiori di . Infatti poichè un numero composto minore di n possiede sicuramente un divisore minore di perciò cancellando i multipli dei numeri primi minori di si cancellano automaticamente tutti i numeri composti minori o uguali a n.

Se, per esempio, vogliamo determinare i numeri primi positivi minori di 100, dalla sequenza

 2,3,.........................,100

dobbiamo cancellare tutti i multipli di 2, di 3, di 5 e di 7.