Eratostene, crivello di
Eratostene, crivello di algoritmo per la determinazione dei numeri primi inferiori o uguali a un dato numero naturale n. Il metodo consiste nel “setacciare” (o “crivellare”) successivamente i divisori di un numero fino a ottenere una tabella di numeri primi. Dopo aver scritto una lista contenente tutti i numeri naturali compresi tra 2 e n, si evidenzia il numero 2 e si cancellano tutti i suoi multipli dalla lista. Si ripete il procedimento, evidenziando a ogni passo il primo numero della lista non già evidenziato o cancellato e cancellando tutti i suoi multipli dalla lista. L’algoritmo ha termine non appena si evidenzia un numero il cui quadrato è maggiore di n: i numeri primi cercati sono i numeri che non sono stati eliminati dalla lista.