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: $a = p \times r$ con $\,\!r > p$ .

Se ne deduce che $a = p \times r \ge p \times p = p^2$ 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