Question

Cerința Se citeşte un număr natural n. Să se determine descompunerea în factori primi a lui n. Date de intrare Programul citește de la tastatură numărul n. Date de ieșire Programul va afișa pe ecran factorii primi ai lui n în ordine crescătoare, separați prin câte un spațiu.

Answer 1

Varianta 1) :

Incepem cautarea factorilor primi de la primul numar prim. Cautam factorii primi cat timp i este mai mic decat n

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for(int i = 2; i <= n; i++){
      int exp = 0;
      while(n % i == 0) {
        exp++;
        n = n / i;
      }
      if(exp > 0)
        cout << i <<" la puterea " << exp <<endl;
    }
    return 0;
}

Variata 2):

Programul se poate optimiza daca observam ca poate exista un singur factor prim mai mare decat radicalul numarului. O sa cautam factorii primi pana la radicalul numarului


#include <iostream>
using namespace std;

int main() {
    int n, i;
    cin >> n;
    for (i = 2; i * i <= n; i++){ //cautam factorii primi pana la radicalul lui n
      int exp = 0;
      while(n % i == 0) {
        exp++;
        n = n / i;
      }
      if(exp > 0)
        cout << i <<" la puterea " << exp <<endl;
    }
    // daca n mai contine un factor, el este un numar prim la puterea unu
    if(n > 1)
      cout << n <<" la puterea 1";
    return 0;
}