Newsgroup: it.comp.lang.c++
Titolo: Calcolo di numeri primi...

Problema problemino... sto cercando di risolvere un esercizio che si
trova nel cap. 03 ( è l'esercizio 2 ) del libro del nostro amico Bruce.
Chiede di calcolare numeri primi usando due cicli for innestati e
l'operatore %.
Io ho provato in tutti i modi, ma come potete vedere non ce l'ho fatta.
Quello che mi è saltato fuori è questo:
#include<iostream>
using namespace std;
int main() {
    for (int i_a = 1; i_a < 100 ; i_a++) {
        if (i_a % 1 == 0) {
            for (int i_b = 1; i_b <= i_a; i_b++) {
                if (i_a % i_b == 0 && i_a == i_b)
                cout << i_a << endl;
            }
        }
    }
}
Purtroppo mi stampa tutti i numeri. Qualcuno mi può aiutare???
Ringrazio e saluto.CiozZ!!!

Ciao!
Questo problema e' stato ampiamente dibattuto poche settimane fa, il
thread era intitolato "Esercizio in c++". Se come sospetto e' gia'
sparito dal tuo reader puoi recuperarlo su un motore di ricerca tipo
http://www.deja.com/
Ciao,
Nicola


Purtroppo sono troppo impulsivo ( anche se ho aspettato molto prima di
postare nel NG ).
E' ovvio che mi stampi tutti i numeri; ho modificato cosi il secondo if:
if (i_a % i_b == 0 && i_a == i_b && i_a % 2 != 0 && i_a % 3 != 0 && i_a %
5 != 0)
così sembra andare, anche se non ho controllato se sono tutti giusti ( in
teoria ci sono i numeri divisibili per 7 );  ho controllato ci sono i
numeri divisibili per 7 ( es. 49 ).
Allora adesso il problema è un altro: come posso fare a eliminare tutti i
numeri divisibili per numeri primi senza continuare ad aggiungere &&
nell'if?
Ringrazio e mi scuso per l'ingenuità. CiozZ!!!

Nicola Musatti wrote:

Ho provato ad andare nel sito, mi da un sito di informazioni per gli
acquisti... Non
e' che l'URL e' vecchio? O sto sbagliando io?...

In realta' in quella pagina c'e' un link, ma e' poco visibile l'URL del
motore e' 
http://www.deja.com/usenet/
Ciao,
Nicola

 >                 if (i_a % i_b == 0 && i_a == i_b)
La seconda parte dell'&& ti dice che l'intero ciclo
annidato che stai facendo e` del tutto inutile poiche`
poi vai a far qualcosa di concreto solo per l'ultimo
valore di i_b (l'istante in cui diviene eguale ad i_a
nella tua impostazione del ciclo interno).
La logica deve essere invece: controlla la divisibilita`
di i_a per TUTTI i valori rilevanti di i_b (da 2 a i_a-1,
vedi sopra); se ne trovi ANCHE SOLO uno -- i_a NON
e` primo.
Devi dunque ricordare se nel corso del ciclo hai mai
trovato un caso di divisibilita`, poiche` l'azione di
stampa puoi compierla, dopo che il ciclo e`finito, se
e solo se NESSUNA divisibilita` e` stata riscontrata.
Puoi tenere traccia di questo in vari modi, ma il
piu` semplice e limpido e`sicuramente quello di
introdurre un'ulteriore variabile di tipo bool.
Nota che questa variabile deve sicuramente avere
un valore iniziare false prima di cominciare il
ciclo (non hai ancora visto nessuna divisibilita`)
e, piccola ottimizzazione, puoi terminare il ciclo
se mai la variabile bool in questione diventa true
(non c'e` nessun danno ad arrivare sino alla fine,
ma e` inutile, visto che sai gia` che non stamperai
i_a qualunque altra cosa succeda nel ciclo).
Buon lavoro!
Alex

                 if (i_a % i_b == 0 && i_a == i_b)
Che significa???
Io mettereti al posto del secondo for:
bool trovato = false;
int i_b = 2;
while(!trovato && i_b <= sqr(i_a)) {
  if ((i_a % i_b) == 0) {
     trovato = true;
  }
}
if (!trovato) cout << i_a;
--
| /
| \Byte - Andrea Briganti
E-Mail 
kbyt...@freemail.it
ICQ 40872731

 per un valore maggiore del suo quadrato è 0
                                     ^
Immagino che intendessi dire radice quadrata, ma in questo caso non e'
vero, ad es. 27 / 9 = 3, mentre la sua radice quadrata e' minore di 6.
Quello che e' vero e' che se un numero ha un divisore superiore alla sua
radice quadrata allora ne ha almeno uno minore.
Ciao,
Nicola

 per un valore maggiore del suo quadrato è 0
Il fatto che un numero intero diviso per qualsiasi numero
maggiore di lui (a maggior ragione quindi se maggiore
del suo quadrato) sia zero e` qui irrilevante.
La ragione per cui (come ottimizzazione, senza effetto
alcuno sulla correttezza) si puo` limitare questo ciclo
con i_b*i_b <= i_a e` invece che, se un numero A e`
esattamente divisibile per un altro numero B maggiore
della sua radice quadrata, lo e` anche per il numero
    C=A/B
che e` minore della radice quadrata di A.
Alex

 del suo quadrato) sia zero e` qui irrilevante.
Maggiore della sua radice quadrata, cmq l'esempio era scritto bene, mi ero
solo confuso a scrivere!
Il codice lo avevo scritto bene usando sqr


 vero, ad es. 27 / 9 = 3, mentre la sua radice quadrata e' minore di 6.
Certamente intendevo radice quadrata, non avrei scritto sqr altrimenti!!!
:-)
Guarda che il tuo ragionamento è errato.
Tu vuoi calcolare se 27 è numero primo vero?
Allora inizi dividendo per 2..... niente....
Allora dividi per 3.... il numero non è primo, non hai nessuna necessità di
arrivare fino a nove.
Fai lo stesso procedimento con gli altri numeri e noterai che il discorso
non cambia.
Prova invece a fare la stessa cosa con un numero primo, vedrai che la
divisione intera del numero per uno maggiore della sua radice quadrata è
sempre 0, il che rende inutile continuare la ricerca.


Guarda che stiamo dicendo la stessa cosa:
Se un numero ha un divisore maggiore della sua radice quadrata ne ha
anche uno minore, come nel caso del 27. Ne consegue, come giustamente
dici tu, che se un numero NON ha divisori minori della sua radice
quadrata, non ne ha neanche maggiori e quindi e' inutile cercare oltre.
Ciao,
Nicola

 solo confuso a scrivere!
L'affermazione cosi` modificata, che verrebbe "ogni
numero diviso per un valore maggiore della sua radice
quadrata e` zero", continua ad essere falsa.
Immagino che tu ti sia ulteriormente confuso ora a
correggere cio` che ti eri precedentemente confuso
a scrivere, e intenda qualcosa di ANCORA diverso.
Nessuno dice che l'ottimizzazione che probabilmente
hai in mente modifichi la correttezza dell'algoritmo
(il lemma cruciale e`: se un intero A e` divisibile per
B<A, e B*B>A, allora A e` divisibile anche per un numero
C<A tale che C*C<A; e` anche di facile dimostrazione).
Ma a chi non riesce a sviluppare correttamente anche
il piu` semplice e limpido algoritmo di ricerca dei
numeri primi, non si fa certo un favore a consigliare
di inserire ottimizzazioni... PRIMA garantire che i
risultati siano corretti, POI, se mai, ottimizzare.  A
maggior ragione, se le ottimizzazioni sono giustificate
con affermazioni errate (e poi corrette in modi tali da
produrre _ulteriori_ affermazioni errate...) e, tanto
per soprammercato, implementate in modi dubbi
(nessun bisogno di calcolare la radice quadrata, che
e` tipicamente un'operazione computazionalmente
costosa, poiche`, fra numeri naturali, A<sqrt(B)
equivale esattamente ad A*A<B).
Infine, non esiste in C++ una funzione sqr, che
hai usato nel tuo codice e continui a nominare.
Per lo meno, non esiste nelle librerie standard.
Presumibilmente, intendi sqrt, e forse ti confondi
con altri linguaggi, come Visual Basic, dove si
usa effettivamente sqr per questo stesso tipo di
calcolo.  Comunque sia, il codice che proponi e
di cui continui a parlare e` anche scorretto per
questa ulteriore ragione.
Alex

per calcolarlo io ho usato un mitico ciclo while...
void main()
{
        int num;
        int scmp;
        cin >> num; cout << endl;
        while (num > 1)
        {
                scmp = 2;
                cout << num << " / ";
                while ( num % scmp != 0 ) scmp++;
                cout << scmp;
                cout << endl;
                num /= scmp;
        }
 
        cout << "1\n\nFound primary number... stopped!\n";
}
adesso non sò se lo scopo era utilizzare proprio due  cicli for
___________________________________________________________
                    _
 \ \// // //| | // |_ _|_|_ member of EventOrizon software
  \//\// // | |//  |_  | |   
http://members.xoom.it/wavexx
___________________________________________________________

Scusami ma avevo cannato di brutto! A volte la memoria fa di questi scherzi:
Ecco il perchè del limite a sqrt(N):
Prendiamo N dispari, lo possiamo definire come N = k*h  se k > sqrt(N)
allora h < sqrt(N) e viceversa.
In poche parole se un numero non ha divisori minori della sua radice
quadrata non avrà neppure divisori maggiori della radice quadrata!


 del suo quadrato) sia zero e` qui irrilevante.
Infatti mi sono accorto che avevo bevuto abbastanza prima di scirvere!!!!
Allora, intanto come ottimizzazione dell'algoritmo si possonono escudere
dalla ricerca i numeri < 4.
Quello che in realtà spiega íl limite sta in questo:
Prendiamo N dispari, lo possiamo definire come N = k*h  se k > sqrt(N)
allora h < sqrt(N) e viceversa.


 questa ulteriore ragione.
Scorretto?
Sicuro? Eppure ti assicuro che il limite per la ricerca dei numeri primi è
proprio quella amata/odiata sqrt(N), controlla con qualsiasi valore di N
(anche se arrivati a un certo punto potrebbe essere necessaria una struttura
dati per evitare di dividere per numeri non primi in modo da ridurre le
operazioni).
Dici che sqrt è una funzione troppo costosa? Bene, si calcola il quadrato
una sola volta e lo si usa per tutte le iterazioni.
Cambia la logica dell'algorimo come l'ho proposto?
No, il limite rimane sempre quello.


 No, il limite rimane sempre quello.
Esiste un'ottimizzazione corretta (una fra tante) che,
quando il candidato e` un numero primo, permette
(spesso; dipende dal costo relativo delle operazioni
di macchina, divisione, moltiplicazione, e radice
quadrata) di risparmiare lavoro.
Il modo in cui hai tentato di esprimere questa ben
nota ottimizzazione, e soprattutto i modi in cui hai
tentato di spiegare perche` funziona, non sono, come
ho gia` illustrato, accettabili da nessun punto di vista.
Alex

 allora h < sqrt(N) e viceversa.
Questo lemma e` corretto (e, in realta`, il fatto
che N sia dispari non gioca in esso alcun ruolo: il
lemma e` altrettanto corretto anche se N e` pari),
e` lo stesso che ho gia` postato l'altro giorno, e
da esso segue la correttezza dell'ottimizzazione.
Se l'ottimizzazione sia effettivamente tale --
dipende.  Il calcolo di sqrt(N) e` tipicamente assai
costoso, e dovrebbe essere fatto per _tutti_
i candidati, anche quelli che falliscono molto
prima che la "ottimizzazione" entri in gioco;
i numeri primi sono relativamente rari, cioe`
la loro densita` non e` gran che, quindi non
e` probabile che questo calcolo si ammortizzi.
Si tratta dunque di confrontare queste due
versioni del ciclo base di controllo (al netto
di dettagli come quello di provare solo divisori
dispari, e altre simili ulteriori ottimizzazioni,
che cambiano poco o nulla della questione
_sostanziale_):
    int posdiv = 2;
    while(posdiv < candid) {
        if(candid%posdiv == 0)
            break;
        ++posdiv;
    }
rispetto al "quasi" identico:
    int posdiv = 2;
    while(posdiv*posdiv < candid) {
        if(candid%posdiv == 0)
            break;
        ++posdiv;
    }
chiaramente il secondo itera meno volte,
ma fa una moltiplicazione in piu` ad ogni
iterazione.
Nella realta`, la moltiplicazione costa molto
meno della divisione (ancor meno costano
i test while o if, e gli incrementi di posdiv)
quindi l'ottimizzazione e` sicuramente tale.
Se non vi fosse questo rapporto di costi, la
convenienza si avrebbe comunque per
candid PRIMI sufficientemente grandi.  Ma
notiamo che molto dipende da _quante
volte si eseguira` *tipicamente* il ciclo_
per un candidato "medio"... che NON e` un
numero primo.
Per dimostrare che questa E` una ottimizzazione,
in presenza di valori parametrici M e D per
i costi di moltiplicazione e divisione (anche
ignorando per semplicita`, cioe` supponendoli
trascurabili rispetto a questi, tutti i costi dei
vari test/incrementi/ecc), si deve fare uno
studio molto piu` preciso delle "densita`"
statistiche della variabile "piu` piccolo divisore
di un generico intero ``candid''".  Non e` proprio
roba da tesi di laurea in analisi numerica, ma non
siamo poi lontani:-).
Alternativamente, si puo` MISURARE l'effettivo
impatto dell'ottimizzazione, per vedere se vale
la pena di averla (magari su diverse macchine).
E` un approccio in generale molto piu` semplice
dell'analisi matematica esaustiva, e questo lo
rende di solito preferibile, nonostante i suoi ovvi
limiti quanto a generalita`.
*Naturalmente*, occorre disporre PRIMA di
una versione "di base" dell'algoritmo, una NON
ottimizzata, ma corretta.  E` assurdo fare delle
ottimizzazioni prima di avere fatto funzionare
le cose...!-)
Alex