Il Crivello di Eratostene

Nel corso dei secoli sono stati fatti numerosi tentativi per determinare un algoritmo capace di generare solo numeri primi, e sono state fatte numerose congetture sulla primalità dei numeri appartenenti a determinate classi, alcune di queste congetture sono state in seguito smentite, altre sono ancora da dimostrare.
Il sistema più semplice per ricercare i numeri primi minori di un certo numero N è stato ideato da Eratostene di Cirene, matematico e filosofo greco vissuto nel II secolo a.c., ed è noto con il nome di CRIVELLO DI ERATOSTENE.


Si tratta di una specie di setaccio che scarta i
numeri composti e permette così di trovare i numeri primi.

Supponiamo, ad esempio, di voler trovare i numeri primi minori di 100. Scriviamo tutti i numeri compresi tra 1 e 100 in una tabella. Il numero uno viene cancellato perché non è un numero primo.

Il primo numero è 2: si cancellano tutti i multipli di 2 (2 escluso);
il primo numero che resta è 3: si cancellano tutti i multipli di 3;
il primo numero che resta è 5: si cancellano tutti i multipli di 5

poiché la radice quadrata di 100 è 10, l'ultimo numero di cui cancellare i multipli è 7; una volta cancellati i multipli di 2, 3, 5, 7, i numeri che restano sono tutti e soli i numeri primi minori di 100.