Răspuns :
Asa arata in C++ (ce faci tu la scoala):
bool CheckPrime(int Nr){
bool IsPrime=true;
if(Nr!=2){
if(Nr%2!=0){
for(int x=3;x<=sqrt((double)Nr);x+=2){
if(Nr%x==0) IsPrime=false;
}
return IsPrime;
}else{
return false;
}
}else{
return true;
}
}
De fapt acest algoritm verifica daca un numar e prim...dar seamana cu ce vrei tu.
Ce faci e practic impartirea numarului Nr(caruia vrei sa-i aflii nr. prime) la toate numerele prime. Insa verifici ,mai intai daca numarul e par. Daca e par atunci verifici de cate ori se poate impartii la 2. Apoi continui cu 3,5,7,9,11,13,17,23....etc.
O metoda(slaba):
citeste nr;
nr_prim <-- 2 //aici va fi pus numarul prim la care vom impartii nr.
cat timp nr<>1
daca nr%nr_prim=0 atunci
nr <-- nr/nr_prim //elimina nr.prim din Nr.
afiseaza nr_prim
//daca numarul se imaprte la nr. prim atunci...AFISEAZA-l
altfel
daca nr_prim =2 atunci
nr_prim=3
altfel
nr_prim <--nr_prim +2
//daca nu e doi atunci poti aduna cu 2..Ex. daca nr_prim e 3 atunci +2 va fi 5 (POATE fi impar..daca adunam cu 1 da 4...si stim ca fiind par si diferit de 2 nu e prim deci e inutil sa-l punem la socoteala...pe el sau orice alt numar par..deci ne trebuie doar nr. impare ! deoarece multe dintre numerele prime sunt impare
inchide altfel
inchide daca
repeta
Ex.: daca Nr=4 (= 2*2 ->nr. prime)
nr_prim e 2 //initial
nr%nr_prim e 0 (restul impartirii lui 4 la 2 e 0) deci scapa de doi din 4 prin impartire si afiseaza 2.
Acum Nr e 2 (am facut impartirea).
REPETAM
nr%nr_prim e 0(restul impartirii lui 2 la 2 e 0) deci scapa de doi din 2 si afiseaza 2
Acum Nr e 2/2 care 1..loop-ul se termina
Insa daca Nr. era 2*3*5 (30) ?
Mai intai il impartea la 2 si 30 impartit la 2 da restul 0 deci ar fi afisat 2. Ramane Nr =30/2=15 (prin imaprtire)
La urmatorul ciclu 15 nu se mai imaprte perfect la 2 (da restul 1) deci va intra in ALTFEL (e o conditie acolo). Si daca nr_prim e doi fa-l 3 (urmatorul nr. prim).
La urmatorul ciclu 15 se imaprte perfect la 3 deci va afisa 3 iar Nr va deveni 5.
Insa la urmatorul loop 5 nu se mai imparte la 3 si va aduna in nr_prim +2 adica nr_prim va fi 5..si la urmatorul ciclu va fi si acesta afisat...
bool CheckPrime(int Nr){
bool IsPrime=true;
if(Nr!=2){
if(Nr%2!=0){
for(int x=3;x<=sqrt((double)Nr);x+=2){
if(Nr%x==0) IsPrime=false;
}
return IsPrime;
}else{
return false;
}
}else{
return true;
}
}
De fapt acest algoritm verifica daca un numar e prim...dar seamana cu ce vrei tu.
Ce faci e practic impartirea numarului Nr(caruia vrei sa-i aflii nr. prime) la toate numerele prime. Insa verifici ,mai intai daca numarul e par. Daca e par atunci verifici de cate ori se poate impartii la 2. Apoi continui cu 3,5,7,9,11,13,17,23....etc.
O metoda(slaba):
citeste nr;
nr_prim <-- 2 //aici va fi pus numarul prim la care vom impartii nr.
cat timp nr<>1
daca nr%nr_prim=0 atunci
nr <-- nr/nr_prim //elimina nr.prim din Nr.
afiseaza nr_prim
//daca numarul se imaprte la nr. prim atunci...AFISEAZA-l
altfel
daca nr_prim =2 atunci
nr_prim=3
altfel
nr_prim <--nr_prim +2
//daca nu e doi atunci poti aduna cu 2..Ex. daca nr_prim e 3 atunci +2 va fi 5 (POATE fi impar..daca adunam cu 1 da 4...si stim ca fiind par si diferit de 2 nu e prim deci e inutil sa-l punem la socoteala...pe el sau orice alt numar par..deci ne trebuie doar nr. impare ! deoarece multe dintre numerele prime sunt impare
inchide altfel
inchide daca
repeta
Ex.: daca Nr=4 (= 2*2 ->nr. prime)
nr_prim e 2 //initial
nr%nr_prim e 0 (restul impartirii lui 4 la 2 e 0) deci scapa de doi din 4 prin impartire si afiseaza 2.
Acum Nr e 2 (am facut impartirea).
REPETAM
nr%nr_prim e 0(restul impartirii lui 2 la 2 e 0) deci scapa de doi din 2 si afiseaza 2
Acum Nr e 2/2 care 1..loop-ul se termina
Insa daca Nr. era 2*3*5 (30) ?
Mai intai il impartea la 2 si 30 impartit la 2 da restul 0 deci ar fi afisat 2. Ramane Nr =30/2=15 (prin imaprtire)
La urmatorul ciclu 15 nu se mai imaprte perfect la 2 (da restul 1) deci va intra in ALTFEL (e o conditie acolo). Si daca nr_prim e doi fa-l 3 (urmatorul nr. prim).
La urmatorul ciclu 15 se imaprte perfect la 3 deci va afisa 3 iar Nr va deveni 5.
Insa la urmatorul loop 5 nu se mai imparte la 3 si va aduna in nr_prim +2 adica nr_prim va fi 5..si la urmatorul ciclu va fi si acesta afisat...
Vă mulțumim că ați vizitat platforma noastră dedicată Informatică. Sperăm că informațiile oferite v-au fost utile. Dacă aveți întrebări sau aveți nevoie de asistență suplimentară, nu ezitați să ne contactați. Așteptăm cu nerăbdare să vă revedem și nu uitați să ne salvați în lista de favorite!