Newsgroup: it.comp.lang.c++
Titolo: Numero primo

Salve ragazzi sto facendo una funzione in C++ che mi calcoli se un numero è
primo, oppure no. Ho usato un metodo iterativo, che controlla il numero per
quali numeri è divisibile, partendo da 2 fino ad arrivare al numero stesso.
Questa maniera piò risultare efficace se il numero in questione è piccolo,
ma è una soluzione lentissima se il numero è grande. Comunque posto la mia
funzione, in attesa che qualcuno mi voglia dare una mano.
bool calcolo(int n)
{
        for (int j=2; j<n; j++)
        {
 
                if (!n%j)
                        return false;
        }
return true;
}
-- 
ICQ # 84624356
MSN 
lello...@katamail.com
Yahoo ilpuntatore

E' sufficiente qualche semplice accorgimento per migliorare
notevolmente le prestazioni:
bool calcolo(int n)
{
        if (! n%2) return false;
        int radice = int( sqrt(n) )
        for (int j=3; j<=radice; j+=2)
        {
                if (!n%j)  return false;
        }
       return true;
}
con queste modifiche vengono considerati soltanto i numeri dispari fino
alla radice di n.
Per es. per testare se 2010545359 e' primo bastano circa 22 mila
confronti invece di 2 miliardi, e il tempo di esecuzione passa dal
minuto a qualche millisecondo.
Ovviamente per numeri molto piu' grandi (centinaia di cifre) il
problema resta comunque intrattabile.
Saluti,
Fabio

 }
ok,  allora ....
alcune idee che mi vengono:
- (!n%j) non va bene.... ti serve (!(n%j)), ma penso questo lo sapessi.
- se testi due e inizi il ciclo da 3 poi puoi proseguire di due in due 
dimezzando il numero di iterazioni.
- non importa arrivare fino ad n, basta arrivare fino a sqrt(n)+1, in questo 
modo riduci la complessita' computazionale da n a sqrt(n) (e contando la 
cosa di prima a sqrt(n)/2).
in pratica se prima ci mettevi 1.000.000 di iterazioni ora ce ne metti: 500. 
Se ogni iterazione richiedeva 1ms prima ci volevano oltre 16 minuti, ora 
mezzo secondo (i dati sono puramente indicativi).
sono convinto che da qui si possa ancora procedere in meglio ma da qua in 
poi dovrei mettermi a studiare l'argomento invece di limitarmi a queste 2 
idee venute in mezzo secondo.
so che ci sono algoritmi estremamente veloci che se ti dicono che un numero 
non e' primo allora non lo e', ma se ti dicono che e' primo c'e' invece una 
minima possibilita' che non lo sia.... Vedi Miller-Rabin e company... Questi 
algoritmi probabilmente non fanno al caso tuo, ma se cio' fosse puoi 
documentarti.
Ad ogni modo ecco la mia soluzione (partendo dalla tua e modificandola):
<CODE>
bool calcolo(unsigned n)
{
    bool ret = true;
    if(n==2)
        ;    // null statement: 2 is prime
    else if(!(n%2))
        ret = false;
    else
    {
        unsigned sq = MySqrt(n) + 1;
        for(unsigned j=3; j<=sq; ++j){
            if(!(n%j))
            ret = false;
        }
    }
    return ret;
}
</CODE>
dove MySqrt() e' una funzione che calcola la radice quadrata di n ed e' 
ottimizzata per interi. Alternativamente (nella maggior parte dei casi) 
puoi usare quella fornita dalla libreria cmath che lavora su doubles ma 
tanto viene eseguito una sola volta per funzione e di solito sqrt e' cmq 
parecchio ottimizzata (c'e' caso che lo sia tanto che non ti convenga 
affatto farne una tu).
Tommaso

 for(unsigned j=3; j<=sq; ++j){
chiaramente intendevo:
for(unsigned j=3; j<=sq; j+=2){
Tommaso

 - non importa arrivare fino ad n, basta arrivare fino a sqrt(n)+1, in
questo
perche' sqrt(n)+1 e non sqrt(n) ?
Forse intendi che la condizione del ciclo deve essere j < sqrt(n)+1 ??
Ciao

 </CODE>
Pensavo all'aggiunta di un'ulteriore controllo prima del ciclo:
 if ((n - static_cast<int>(n / 10) == 5) && (n != 5))
  return false;
Infatti i numeri terminanti con 5 (5 escluso) non possono mai essere primi
essendo sempre multipli di 5.

 essendo sempre multipli di 5.
questo equivale ad aggiungere una divisione per 5 e controllare che non 
ci sia resto. E viene già fatto all'interno del ciclo, posto che il 
numero da verificare sia >= 25.
-- 
si prepara direttamente nel bicchiere basso detto "tumbler basso". Tre o 
quattro cubetti di ghiaccio, aggiungere il gin, il martini rosso, il 
bitter campari e mescolare. Guarnire con una fetta d'arancia.

 numero da verificare sia >= 25.
Soltanto? Mi pare che anche per n >= 15 questo accada.
Ciao

 Soltanto? Mi pare che anche per n >= 15 questo accada.
Ah, ti riferisci al codice con la radice quadrata allora.
Ciao

 perche' sqrt(n)+1 e non sqrt(n) ?
Ah, arrotondi per eccesso?
Ciao

 Ah, arrotondi per eccesso?
Scusa per i post frammentati ma non riesco a capire perche' metti sqrt(n)+1
e non sqrt(n).
Sai indicarmi un numero n il cui minimo divisore e' sqrt(n)+1?
Grazie

         for(unsigned j=3; j<=sq; ++j){
          for(unsigned j=3; j*j <=n; ++j){
Ed eviti di estrarre la radice quadrata.
Ciao,
Nicola

 </CODE>
CUT
Ti ringrazio molto dell'aiuto, sto facendo alcune prove e penso proprio che
la tua funzione sia molto valida, unica cosa che non comprendo è
quell'if(n==2) e poi ; , dopo la if cosa significa quel punto e virgola?


 Ed eviti di estrarre la radice quadrata.
Gia', ma prima la radice qudrata era estratta una sola volta ora invece 
moltiplichi ad ogni iterazione, quindi non sono sicuro sia piu' veloce... 
;-) (e' meglio estrarre la radice quadrata una sola volta o moltiplicare due 
numeri n volte (dove n puo' essere tranquillamente anche un miliardo e 
perche' no anche molto di piu'?)
Ad ogni modo, il vero problema di fare j*j e' che se, ad esempio, con 
unsigned int di 32 bits vuoi vedere se 1 miliardo e 1 (1,000,000,001) e' 
primo o meno estraendo la radice quadrata puoi, usando j*j invece no.
In pratica usando la radice quadrata puoi sempre fare il primality test per 
ogni valore di n (dove n e' un unsigned int da 0 a 2^32 -1), ovvero da 0 
fino a 4,294,967,295 usando j*j invece ti limiti a poter fare il primality 
test di 65,535. Una bella differenza.
Lo stesso discorso vale per valori a 16 e a 64 bits etc... solo con limiti 
differenti.
Poi ci sono tipi di dato a precisione arbitraria, ok, ma sommando le due 
cose insieme credo sia meglio estrarre la radice.
Tommaso

 quell'if(n==2) e poi ; , dopo la if cosa significa quel punto e virgola?
Ok, forse non e' il massimo dell'eleganza, ma funziona cosi':
inizializzo ret a true, assumendo che sia primo. Quindi se n==2 allora non 
vario il valore, dice gia' che il numero e' primo. Ovviamente pero' non mi 
eseguira' le altre due condizioni e ritornera' subito true.
Mi sono appena accorto che il codice esegue operazioni non necessarie (dopo 
che e' stato trovato che il numero NON e' primo continua ad andare 
avanti....). Mi sono dimenticato nella fretta un "break":
<CODE>
bool calcolo(unsigned n)
{
    bool ret = true;
    if(n==2)
        ;    // null statement: 2 is prime
    else if(!(n%2))
        ret = false;
    else
    {
        unsigned sq = MySqrt(n) + 1;
        for(unsigned j=3; j<=sq; j+=2){
            if(!(n%j)){
                ret = false;
                break;
            }
        }
    }
    return ret;
}
</CODE>
Questo dovrebbe essere molto meglio ;-)
HTH,
Tommaso

 Sai indicarmi un numero n il cui minimo divisore e' sqrt(n)+1?
no, pensandoci bene non credo proprio che il +1 sia necessario e no non so 
quindi indicarti nessun numero per cui ... etc.
Il motivo per cui ho introdotto il +1 e' per numeri come 48 (e non come 49), 
dove altrimenti la radice quadrata intera viene arrotondata per difetto. 
L'algoritmo e' stato scritto in due minuti con idee venute in mente e non 
troppo pensate. Mi sono inizialmente scordato di scrivere il j+=2 (e non 
++j) ed il break. Entrambe le cose erano state pensate ma poi non scritte 
nella fretta. Il +1 invece e' stato pensato e scritto, ma non e' affatto 
indispensabile.
Spero questo chiarisca.
Tommaso

uhm un metodo alquanto contorto...
perche' non fare un bel return al momento giusto invece di trascinarsi
quel ret fino alla fine della funzione ?
Il "single point of exit" (si chiamava cosi?) e' un retaggio del
passato, ormai obsoleto.
Saluti,
Fabio

 ha scritto nel messaggio
news:1113602414.3...@l41g2000cwc.googlegroups.com...

Scherzi? Come ti è venuta questa idea? Le uscite intermedie sono comode ma
sono quasi sempre fonte di problemi, presto o tardi.
EMG
--
EMAG Software Homepage:     
http://www.emagsoftware.it
The EMG's ZX-Spectrum Page: 
http://www.emagsoftware.it/spectrum
The Best of Spectrum Games: 
http://www.emagsoftware.it/tbosg
The EMG Music page:         
http://www.emagsoftware.it/emgmusic

 EMG
Beh, mi riferisco al C++ naturalmente, in C ha senso avere un unico
punto di uscita dove "fare pulizia", ma in C++,  avere un solo return
in fondo alla funzione non garantisce che quello sia l'unico punto di
uscita, perche' in qualunque punto all'interno potrebbe essere
sollevata un'eccezione. Quindi quel singolo punto di uscita da' una
"falsa sicurezza" che il "clean-up" verra' fatto in ogni caso. In
presenza di eccezioni (e in genere non puoi essere sicuro che nessuna
delle funzioni che chiami all'interno del tuo metodo  non sollevi
eccezioni) e' importante utilizzare idiomi come il RAII dove le risorse
vengono allocate da oggetti automatici che le liberano nel distruttore,
in ogni caso,  all'uscita dallo scope.
A quel punto, se scrivi una funzione "exception safe", avere un single
point of exit non ti da' nessun vantaggio in piu', ma soltanto ti
complica il codice con una catena di 'if then else' di difficile
lettura.
Fabio

 lettura.
Così però mi sembra che stai solo spostando il problema, nascondendolo sotto
il tappeto. Ma non insisto in quanto non ho ben chiaro il discorso
sull'"exception safe".


sollevata un'eccezione.
Ma tu sei contro o a favore del singolo punto di uscita? Hai detto 2 cose
diverse in 2 post.
Ciao

 ha scritto:

Ah, ok ho riletto, sei contro :P

 sull'"exception safe".
Considera per esempio le due funzioni qui sotto:
int f(int x) {
   int ret = 0;
   C1* pc1 = new C1(x);
   C2* pc2  = new C2(x);
   if (x < 0) {
     ret = -1;
   } else if (x<2) {
     ret = pc1->f(x) + pc2->f(x+1);
   } else {
     ret = pc1->f(x-1)+pc2->f(x);
   }
   delete pc1;
   delete pc2;
   return ret;
}
int g(int x) {
   if (x < 0) {
      return -1;
   }
   std::auto_ptr<C1> pc1(new C1(x));
   std::auto_ptr<C2> pc2(new C2(x));
   if (x<2) {
      return pc1->f(x) + pc2->f(x+1);
   }
   return pc1->f(x-1) + pc2->f(x);
}
(Ovviamente sarebbe ancora meglio dichiarare pc1 e pc2 come variabili
automatiche, ma e' tanto per avere un esempio di risorse allocate
all'ingresso e da rilasciare all'uscita, immagina per esempio che C1 e
C2 siano classi astratte e che le istanze concrete vengano allocate
tramite un factory method)
A prima vista le due funzioni sembrerebbero comportarsi allo stesso
modo, ma se una delle chiamate ai metodi C1::f() e C2::f() sollevasse
un'eccezione, nel primo caso le risorse allocate non verrebbero
liberate.
Quindi, un metodo exception-safe deve consentire l'uscita in qualunque
momento (a causa di eccezioni) liberando le eventuali risorse
acquisite. A questo punto, avere un unico return "esplicito" alla fine
non e' di nessun aiuto, visto che potrebbe esserci un return
"implicito" in qualunque altro punto del metodo.
Per ulteriori approfondimenti sull' "Exception Safeness" consiglio gli
ottimi libri di Herb Sutter "Exceptional C++" e "More Exceptional C++"
(Addison Wesley).
Fabio

 wrote

contorto... chi e' abituato a codice C/C++ e' abituato a leggere i null 
statements ad ogni modo ammetto non sia il massimo della eleganza. 
Tuttavia....
bool calcolo(unsigned n)
{
    if(n==2) return true;
    if(!(n%2)) return false;
    unsigned sq = MySqrt(n) + 1;
    for(unsigned j=3; j<=sq; j+=2)
        if(!(n%j)) return false;
    return true;
}
.... nemmeno avere 4 return statements in 6 righe di codice e' molto 
elegante ;-)
(ho ristretto il codice per portarlo a 6 righe ;-)
Vedi tu, credo sia una questione di gusti piu' che altro, specialmente in 
funzioni cosi' brevi e semplici dove C++ e, exceptions e... i libri di 
Sutter che ho letto volentieri non hanno pero' nulla a che fare ;-)
Questa soluzione che ho postato ora non mi dispiace, solo non la credo 
"superiore" a quella con  un solo return (e nemmeno inferiore). Come ho 
detto e' questione di gusti a mio avviso.
Tommaso
P.S. continuo a mettere il piu' 1 anche se non credo sia necessario solo per 
coloro che implementano MySqrt() con numeri in virgola mobile che per loro 
natura sono approssimati... Implementazioni di MySqrt() in virgola mobile 
con abbastanza precisione o implementazioni intere non necessitano il +1 
(almeno questa e' la conclusione a cui sono giunto).

 Considera per esempio le due funzioni qui sotto:
Sě, adesso ho capito quello che intendi ma continuo ad avere i miei dubbi
che le eccezioni da sole ti consentano di eliminare tutti i possibili
problemi derivanti dall'avere piů uscite all'interno della stessa funzione o
blocco. Non riesco ad immaginare (ma forse č un mio limite) un programma
organizzato in modo tale che tutte le situazioni immaginabili siano gestite
con le eccezioni. Io certamente non ci riuscirei.


 con le eccezioni. Io certamente non ci riuscirei.
Non dico che le eccezioni permettano di gestire tutte le situazioni,
anzi.
Il problema e' che le eccezioni "possono" essere sollevate e non si
puo' fare finta di niente
(per es. anche una new puo sollevare un'eccezione).
Una funzione "exception safe" e' abbastanza robusta da "resistere" ad
un eventuale eccezione. Una funzione non "exception safe" potrebbe
causare leakage o altri malfunzionamenti in caso di eccezioni.
Quello che intendo dire, riguardo al "single point of exit", e' che se
una funzione e' "exception safe" puo' avere piu' return perche' tanto
e' in grado di liberare le risorse allocate in qualsiasi frangente.
Mentre una funzione che ha bisogno di un solo punto di uscita potrebbe
causare dei problemi in caso di eccezioni impreviste.
Questo e' particolarmente importante quando si utilizzano librerie
esterne o codice di cui non si conosce (o non si puo' prevedere)
l'esatto comportamento, o che potrebbe venire modificato e sollevare
eccezioni in futuro etc.
Fabio

 causare dei problemi in caso di eccezioni impreviste.
Io comunque vedo i punti di uscita intermedi come un aggravarsi della
situazione già creata dalle possibili eccezioni. Non mi sembra invece
accettabile vedere come solo effetto della presenza di un unico punto di
uscita il dare un falso senso di sicurezza. Allora anche programmare in un
linguaggio ad alto livello dà un falso senso di sicurezza rispetto alla
programmazione ASM? :-)


 uscita il dare un falso senso di sicurezza. 
Il problema e` che le funzioni con un solo return alla fine NON hanno
un unico punto di uscita (tranne casi particolari).
Il falso senso di sicurezza e` proprio questo: pensare di poter fare
pulizia prima dell'unico return (senza RAII), come se la funzione
avesse un unico punto di uscita.
        Mauro

 avesse un unico punto di uscita.
Be', allora questo è vero fin dai primordi dell'informatica e il falso senso
di sicurezza c'è sempre stato. Ma allora perché si insegnava che una
funzione doveva avere un unico punto di uscita? C'è qualcosa che mi sfugge o
c'era qualcosa che sfuggiva prima a chi scriveva libri di informatica?


 c'era qualcosa che sfuggiva prima a chi scriveva libri di
informatica?
No, perche' "prima" non c'erano le eccezioni.
In linguaggi come il C o il Fortran, avere un unico punto di uscita era
senz'altro un'ottima pratica.
Ma in C++ non e' piu' altrettanto valida.
Il C++ comunque offfre uno strumento prezioso per gestire la "pulizia"
in uscita: allocando le risorse nel costruttore di un oggetto
automatico e liberandole nel suo distruttore si ha la certezza che esse
verranno liberate comunque si esca dallo scope dove esso e' stato
istanziato (sia che si esca con un return esplicito che con
un'eccezione sollevata in un qualunque punto dell'esecuzione,
all'interno di quello scope).
Linguaggi con Garbage Collection, come Java o C#, non hanno questa
possibilita' (ma possono comunque adottare tecniche simili, tramite
costrutti try {} finally {},
dove il blocco finally {} viene eseguito comunque si esca dal blocco
try {} ).
Fabio

 No, perche' "prima" non c'erano le eccezioni.
Non c'era la possibilità di intercettarle in modo elegante ma le eccezioni,
intese come eventi esterni che disturbano il normale flusso del programma,
ci sono sempre state. O sbaglio?


 test di 65,535. Una bella differenza.
Tutto questo ovviamente NON col programmino che hai mostrato, dove la
prima operazione che fai e' estrarre la radice quadrata di n, imponendo
quindi che n sia rappresentabile, quindi minore di 4,294,967,296, la
cui radice quadrata e' (sorpresa...) 65536.
In effetti probabilmente il modo per migliorare le prestazioni del tuo
programma e' memorizzare i primi via via in modo da evitare le
divisioni per numeri che non sono primi; insomma, trasformarlo nel
crivello di Eratostene.
Ciao,
Nicola


Non sono d'accordo. Intanto trovo un'ottima cosa distinguere tra le
uscite eccezionali ed il percorso "normale" all'interno della funzione.
In quest'ultimo nella maggior parte dei casi l'utilizzo del singolo
punto di uscita rende piu' evidente l'algoritmo nei suoi passi logici,
soprattutto se si cerca di tenere le condizioni ben separate dal punto
di vista concettuale e di anteporre sempre il ramo relativo al caso
corretto/normale degli if rispetto a quelli relativi a casi
scorretti/anormali.
L'uso di molteplici uscite dal codice mette in evidenza le condizioni
erronee/eccezionali di una funzione, a scapito del suo algoritmo.
Tutt'al piu' puo' avere senso verificare immediatamente se i parametri
soddisfano il contratto della funzione e lanciare immediatamente
un'eccezione in caso contrario.
Ciao,
Nicola


Questo confronto non e' "fair". Considera invece
int h(int x) {
  int ret = -1;
  if ( x >= 0 ) {
    std::auto_ptr<C1> pc1(new C1(x));
    std::auto_ptr<C2> pc2(new C2(x));
    if ( x < 2 )
      ret = pc1->f(x) + pc2->f(x+1);
    else
      ret = pc1->f(x-1) + pc2->f(x);
  }
  return ret;
}
E' altrettanto sicura della tua, non alloca risorse inutilmente e rende
manifesto il fatto che il calcolo del valore di ritorno dipende da
un'insieme di condizioni sul parametro di ingresso, evitando confusioni
tra la gestione di argomenti fuori dominio ed il calcolo "normale" del
valore della funzione.
Ciao,
Nicola


Mi rendo conto che per chi scrive codice con return molteplici lo
svolgimento dello stack che segue il lancio di eccezioni costituisce un
supporto fondamentale per evitare di duplicare il codice di cleanup, al
punto che mi viene il dubbio che questo sia lo scopo fondamentale delle
eccezioni stesse :-)
E' altrettanto vero che, in *totale* assenza di eccezioni la gestione
del cleanup e' quasi sempre piu' pulita nelle funzioni con singolo
punto di uscita.
Pero' siamo nel 2005 e questo e' il C++; la necessita' di scrivere
codice che tenga conto delle eccezioni e' comune a entrambe i campi.
Tra parentesi il "falso senso di sicurezza" di cui parlate tu e Fabio
colpisce anche chi, scrivendo codice con return multipli, si aspetta
che il flusso del controllo arrivi indenne fino al prossimo return.
In questo contesto sono convinto che sia opportuno distinguere quattro
aspetti nel codice:
- La gestione di situazioni eccezionali individuate localmente
Ad esempio la violazione di una precondizione da parte degli argomenti
passati a una funzione. A mio avviso e' un controllo da fare
all'ingresso della funzione e, in caso di problemi, e' opportuno
lanciare un'eccezione o far fallire un'asserzione. Il liberarsi
prontamente di questi casi "anomali" porta a una migliore separazione
tra comportamento normale e comportamento eccezionale, con l'effetto di
semplificare l'algoritmo vero e proprio.
- La gestione di eventi eccezionali che la funzione corrente
  non puo'/deve gestire.
Un'eccezione lanciata da strati piu' bassi dell'applicazione che il
livello corrente non sa come gestire. In questo caso il massimo che si
puo' fare e' usare RAII per assicurarsi di rilasciare sempre risorse
acquisite localmente e cercare di posporre tutte le modifiche
permanenti allo stato dell'applicazione a dopo l'esecuzione di tutte le
operazioni che possono lanciare eccezioni. Questo e' un problema di
disciplina di programmazione sostanzialmente indipendente dalla datriba
singoli/multipli return.
- Il normale flusso del codice
Ovvero l'effettiva implementazione dell'algoritmo che risolve il
problema per cui si scrive la funzione. Personalmente trovo che in
genere l'uso del return singolo porta a codice piu' pulito dal punto di
vista logico, anche se questo richiede una certa disciplina nella
espressione delle condizioni e nel rispettivo collocamento dei rami di
istruzioni condizionali.
- La gestione esplicita di eccezioni
Questa non puo' che trovarsi sparsa nel codice, in funzione di quali
operazioni possono lanciare eccezioni da gestire. A mio avviso
l'effetto benefico sulla chiarezza del codice e' discutibile sia che si
tratti di codice con return singolo sia che vi siano molteplici return.
Tutto va bene se tutte le possibili eccezioni intercettate devono
causare l'interruzione dell'algoritmo normale; in questo caso il codice
risiede nel singolo blocco try. Nella mia esperienza pero' non e'
sempre cosi' e puo' capitare di avere porzioni di codice rese poco
comprensibili dalla presenza di pu' try/catch che avvolgono poche
istruzioni.
In ogni caso stiamo parlando di situazioni che dovrebbero verificarsi
raramente all'interno del codice, perche' la maggior parte delle
funzioni dovrebbe essere sufficientemente semplice da rendere
sostanzialmente superflua la distibnzione tra return singoli e return
multipli.
Ciao,
Nicola

 crivello di Eratostene.
Si, ovvio, o anche solo precomputare i primi n numeri primi e fino al valore 
dell'n-esimo numero primo siamo a posto e non abbiamo testato numeri non 
primi, da li in poi si procede come l'algoritmo sopra (di due in due).
Tommaso

 perche' no anche molto di piu'?)
Per esempio su un PPC dove passare da int a float e viceversa e`
parecchio costoso, la faccenda diventa molto rilevante. Comunque se si
fa "una volta sola" (e quindi una volta sola anche la conversione ad
int) dovrebbe essere trascurabile.
-- 
[ RiK0                                ]
[ Go away! The internet is full!      ]
[ Non credo negli schemi non vincenti ]