Cos’è il crivello e come utilizzarlo?
Il modo più semplice, e anche il più antico. Per la sua semplicità è attualmente usato in numerosi software per la generazione di numeri primi, in quanto l’algoritmo è facilmente implementabile anche se non molto efficiente in termini di prestazioni. Per prima cosa si costruisce una tavola con tutti i numeri naturali da 1 a 100 e si incomincia ad eliminare i multipli di due, escluso il numero stesso: 4, 6 ,8, 10 … Poi i multipli di tre: 9, 15 … visto che il 6 e 12 sono già eliminati. Poi seguiranno i multipli di 5 e di 7. Si otterranno i numeri primi che derivano dalle successive eliminazioni. Come esempio vediamo la seguente tavola.
Una osservazione interessante è che il crivello termina quando si arriva a 10 che è la radice quadrata di 100. In generale per trovare tutti i primi minori di un numero N è sufficiente realizzare un crivello per i numeri primi minori o uguali a √N. Questo ci dà un metodo per trovare i primi minori di un numero dato, che ancora oggi si continua ad usare per trovare i numeri primi piccoli, diciamo fino a diecimila milioni.
I numeri usati nel crivello e quelli che restano dopo le varie cancellazioni sono tutti numeri primi. Interessante questa animazione anche col listato.
È facile comprendere che raggiunto un certo livello la complessità diventa eccessiva. Tale da rendere necessario il ricorso a strumenti di calcolo alternativi, quali il calcolo distribuito.