Question

Cum arata algoritmul de descompunere in factori primi?(pseudocod)

Answer 1

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...