Newsgroup: it.comp.lang.delphi
Titolo: crivello di Eratostene

Ho implementato in Delphi il crivello di Eratostene: un metodo semplice per
estrarre i numeri primi dai numeri naturali.
L'algoritmo mi sembra veloce (90 millisecondi per estrarre tutti i numeri
primi su 1.000.000 di naturali - senza visualizzazione sulla ListBox),
quello
che rallenta é sicuramente il riempimento della ListBox e tutte le
conversioni da numero a stringa.
Ho alternative ? Anche considerendo che
voglio mantenere la possibilità di salvare i dati trovati su un file ?
Posto il codice e un po' di commento.
Grazie per l'interesse, a risentirci.
//----------------------Crivello di Eratostene-----------------------------
//Eratostene (276-194 a.C.) bibliotecario della grande biblioteca di Ales-
//sandria, fu uno degli uomini più brillanti dell'antichità. Probabilmente
//il suo risultato più notevole é stata la misurazione del raggio della ter-
//ra (in un tempo in cui pochi credevano che fosse sferica) ottenuta con-
//frontando le lunghezze delle ombre proiettate da due aste a mezzogiorno
//ad Alessandria e a Siene (oggi Assuan). Ma i teorici dei numeri lo
ricorde-
//ranno sempre per il suo meraviglioso crivello per i NUMRI PRIMI. Così come
//il mugnaio separa il prezioso grano dall'inutile pula, allo stesso modo
//Eratostene usò il suo crivello per separare i preziosi NUMERI PRIMI dai
loro
//comuni compagni COMPOSTI. Funziona così.
//Prendiamo (per es.) i primi trenta numeri naturali (1,2,3...30); scartiamo
//il numero 1 perché considerato una classe speciale; il primo NUMERO PRIMO
//é il numero 2; teniamo il due ed eliminiamo tutti i suoi multipli, quindi
//il 4,6,8,...30; il prossimo numero considerato é il 3; teniamolo ed elimi-
//niamo tutti i suoi multipli (3,6(già eliminato prima dal 2),9...27,30(già
//eliminato prima); il prossimo NUMERO PRIMO della lista é il 5 (il 4 é sta-
//eliminato in quanto multiplo di 2); quindi eliminiamo i multipli di 5 che
//sono: 10,15,20,25,30;, ma di fatto sono solo il 25 perché tutti gli altri
//erano o multipli di 2 o di 3;  A questo punto ci fermiamo perché 5 é, nel
//nostro caso, l'ultimo numero naturale che soddisfa p^2<=N (5 al quadrato é
//minore-uguale di 30) ovvero: la radice intera di N deve essere
minore-ugua-
//le di p(che é come la esprimiamo nel codice del programma). Secondo questa
//regola dei NUMERI PRIMI, quindi, se provassimo a scartare dal nostro esem-
//pio i multipli di 7 faremmo un lavoro inutile in quanto  14 e 28 sono già
//già stati scartati dal 2 mentre il 21 é stato eliminato dal 3.
//Aggiungete al form una LISTBOX e associate il codice sotto ad una qualche
//procedura
//Potete far girare il programma anche per N piuttosto grandi, l'ho provato
//con a N=5.000.000; concluso in una ventina di secondi su AMD 1800.
var k,i,sqrtN: Integer;
    crivello: array of boolean;
const N=100;               //calcola NUMERI PRIMI sui primi 100
                           //numeri naturali
BEGIN
  SetLength(crivello,(N+1));           //dimensiona l'array dinamicamente
  for i:=2 to N do crivello[i]:=true; //riempie array; tutto = a True
  sqrtN:=trunc(sqrt(N));              //calcola la radice intera di N
  for k:=2 to sqrtN do          //la radice intera di N é un limite max
    if crivello[k] then         //se k è un numero primo...
       begin
        i:=k*k;                //partendo dal quadrato di k che è il
                               //primo numero composto...
        while i<=N do          //finché limite max dell'indice dell'array...
         begin
          crivello[i]:= false;   //elimina tutti i multlipli di K
          inc(i,k);              //itera il processo a passi di k
         end;
       end;
  ListBox1.Visible:= False;   //si risparmia un pò di tempo durante
                              //il riempimento della lista
  for i:= 2 to N do begin    //i numeri primi sono tutti gli elementi
    if crivello[i] then      //dell'array con indice = true
    ListBox1.Items.Add(inttostr(i))  //scrivi tutti i numeri primi nella
  end;                               //ListBox
  ListBox1.Visible:=True;
    ListBox1.Items.Add('trovati '+ (inttostr(ListBox1.Count))+ ' primi');
 end;                             //conta i numeri primi trovati

 conversioni da numero a stringa.
Io ci ho provato ma non sono riuscito a migliorare... comunque, invece di
nascondere la listbox, puoi usare Items.BeginUpdate e EndUpdate. Mi dispiace
di non poterti essere piů d'aiuto di cosě :(
--
Jax
====
"Io la prima volta che ha preso un virus mi sono fatto ricoverare con lui"
Beppe Grillo

//sandria, fu uno degli uomini più brillanti dell'antichità. 
Non aggiungo nulla al tuo codice, ma un commento che mi sovviene e' che questo
Erastotene era un grande! :-)
-- 
Morde. 
(
mo...@despammed.com
)
M-List di icld: 
http://it.groups.yahoo.com/group/icld/

 voglio mantenere la possibilità di salvare i dati trovati su un file ?
puoi provare a creare una tstrings in memoria, compilare quella e solo al
termine associala ad un componetne visuale. In linea puramente teorica
dovresti risparmiare tutto il tempo necessario per aggiornare i componenti
visuali ogni volta che ci scrivi dentro.
ciao
z.

 Erastotene era un grande! :-)
Mi trovi d'accordo. Ti correggo l'inversione...si scrive ERATOSTENE.

 visuali ogni volta che ci scrivi dentro.
Ma già disattivando la visibilità del componente non ottengo la stessa cosa
?
Comunque voglio provare anche questa appena ho un po' di tempo, ma ho
paura che il risparmio sia poco, perché alla fine bisogna convertire
da intero a stringa... e uno alla volta.
Grazie.
Ciao

 di non poterti essere piů d'aiuto di cosě :(
Proverň anche questa...grazie

Mi trovi d'accordo. Ti correggo l'inversione...si scrive ERATOSTENE.
Argh... speravo che il mio scempio passasse inosservato.... ;-)
-- 
Morde. (
mo...@despammed.com
)
M-List di icld: 
http://it.groups.yahoo.com/group/icld/
Firefox, il miglior browser: 
http://www.mozilla.org/products/firefox/

 da intero a stringa... e uno alla volta.
prova invece a scrivere su un file di testo con Writeln
var
  F: TextFile;
begin
  AssignFile(F, 'Output.txt');
  try
    Rewrite(F);
  //..
    Writeln(F, VALORE1 {,VALORE2, VALORE_N};
  finally
    CloseFile(F)
  end
end
-- 
Mauro Falzari 
   [ 
http://digilander.libero.it/mauro.falzari
 ]
 
 "Se guardi nell'abisso, anche l'abisso guarda in te." 
   (Friedrich Nietzsche)