Newsgroup: it.hobby.enigmi
Titolo: Crivello di Eratostene

Premessa:
In questi giorni la maestra di mia figlia (IV elementare) sta introducendo i
numeri primi (e mi pare un'ottima decisione! :-) ). Dal momento che temo
che, anche se in buona fede, le potrà scappare di dire che 1 è un numero
primo, la voglio "bloccare" prima possibile e fornirle della documentazione
che la metta al corrente in merito a quale opinione ha la matematica
riguardo al numero 1.
Ho fatto qualche ricerca e ho trovato quanto mi serve su wikipedia.
Tra l'altro ho trovato anche il crivello di Eratostene (anche su questo la
maestra ha fatto un accenno), con tanto di algoritmo. Qui con la maestra mi
fermerei perché penso che non si spingerà tanto in là, ma è proprio su
questo che voglio proporre un enigma a voi.
L'algoritmo in questione viene riportato in un - a me ignoto - linguaggio
bash (assomiglia molto vagamente al C, ma credo che chiunque abbia
familiarità con un qualunque linguaggio di programmazione possa capire 
grosso modo che cosa
fa).
Questo è il link alla pagina:
http://it.wikipedia.org/wiki/Crivello_di_Eratostene
, e copincollo il codice
pari pari anche
sotto.
Dando per buono che il codice sia sintatticamente corretto e che fornisca il
risultato aspettato, a me sembra che con poco sforzo si possa intervenire
per renderlo molto più efficiente di quanto sia. Io vedo due possibili
miglioramenti, tanto semplici da introdurre (modifiche di codice ridotte al
minimo), quanto efficienti in termini di miglioramento delle prestazioni
dell'algoritmo.
Siete d'accordo?
Ciao
Giorgio
#!/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

 Siete d'accordo?
Di solito quando si fa un crivello di questo tipo
non si arriva alla meta' dei numeri, ma al primo P
tale che P^2 > Limite.
Inoltre non serve marcare tutti i multipli del
numero primo corrente P, ma solo quelli maggiori o
uguali a P^2, perche' i multipli inferiori saranno
gia' stati marcati.
Al limite si potrebbe anche evitare di mettere
proprio i numeri pari nell'array iniziale, complicando
pero' un po' il codice.
In ogni caso usare la programmazione bash non e'
proprio il massimo, sia dal punto di vista della leggibilita',
che di quello dell'efficienza.
ciao,
g.

 gia' stati marcati.
Et voilà! :-)
Ciao
Giorgio 


Scusa, non pensavo fosse un enigma, credevo di
essere sul gruppo di matematica
e non ho messo lo spoiler.
ciao,
g.

"Giovanni Resta"

Figurati! Nessun problema. E infatti, come enigma, era un po' anomalo.. :-)
Ciao
Giorgio 

 ...
Quando facevo l'ingegnere :o) avevo disegnato un crivello sinusoidale:
http://www.hostfiles.org/files/20060321013649_crivello.gif
Non c'entra con le tue domande, perņ mi sembra carino anche
per una bimba (o una maestrina :o)). Agli incroci con l'asse si
possono contare, oltre che ai primi, il numero dei divisori.
L'uno č rigorosamente ignorato.
Ciao!!!  :o)
Livio


Molto carino!
Penso proprio che lo proporrò alla maestra! ;-)
Ciao :-)
Giorgio