Crivello di Eratostene
Da Wikipedia, l'enciclopedia libera.
Il crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato. Deve il nome al matematico Eratostene di Cirene, che ne fu l'ideatore. È a tutt'oggi utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio di programmazione.
Il procedimento è il seguente: si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio (in programmazione spesso l'elenco è implementato da un array). Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui stesso). Si prosegue così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n. È come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare solo i multipli di 2, il secondo solo i multipli di 3, e così via.
Nel caso n = 50, ad esempio, il procedimento di setacciatura si conclude con il numero 7 perché 7 è il massimo intero il cui quadrato non supera 50 e si può provare che il procedimento di setacciatura per ricercare i primi fino ad un certo numero n cessa sempre quando si supera la radice quadrata di n. Infatti ogni numero a del setaccio iniziale, contenente tutti i numeri naturali non superiori ad un dato n, cade dal setaccio che corrisponde al più piccolo dei suoi divisori primi.
Se indichiamo con p il più piccolo divisore primo di a si ha: 
con 
.
Se ne deduce che 
da cui p è sempre minore o uguale alla radice quadrata di a.
[modifica] Algoritmo
Il seguente algoritmo è scritto in bash scripting.
#!/bin/bash
# sieve.sh
# Crivello di Eratostene
# di Stephane Chazelas
# Si deve invocare con un argomento da linea di comando.
LIMITE_SUPERIORE=$1 # Da linea di comando.
let META=LIMITE_SUPERIORE/2 # Metà del numero massimo.
Primi=( '' $(seq $LIMITE_SUPERIORE) )
i=1
until (( ( i += 1 ) > META )) # È sufficiente verificare solo la metà dei numeri.
do
if [[ -n $Primi[i] ]]
then
t=$i
until (( ( t += i ) > LIMITE_SUPERIORE ))
do
Primi[t]=
done
fi
done
echo ${Primi[*]}
exit 0
[modifica] Voci correlate
Una evoluzione del crivello di Eratostene è rappresentata dal crivello di Atkin, un algoritmo creato circa nel 1999.
