Crivello di Eratostene

Il crivello di Eratostene è un antico algoritmo per calcolare velocemente tabelle di numeri primi fino ad un certo numero n prefissato. È a tutt'oggi uno dei metodi più efficenti per farlo, dato che utilizza solo l'operazione di somma.

L'idea è questa: scrivi tutti i naturali a partire da 2 fino n in un elenco che possiamo chiamare setaccio. Poi comincia a cancellare (setacciare) tutti i multipli del primo numero del setaccio (escluso lui stesso). Prosegui così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n. È come se considerassi dei setacci a maglie vie 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: a = p * r, con r > p. Se ne deduce che a = p * r >= p * p = p², da cui p è sempre minore o uguale alla radice quadrata di a.

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

---

|