#include <iostream>
#include <vector>
using namespace std;

// Funcție pentru descompunerea unui număr în factori primi
vector<pair<int, int>> descompuneInFactoriPrimi(int n) {

    vector<pair<int, int>> factori;
    int divisor = 2;

    while (n > 1) {
        int count = 0;
        while (n % divisor == 0) {
            n /= divisor;
            count++;
        }
        if (count > 0) {
            factori.push_back({divisor, count});
        }
        divisor++;
        // Optimizare: verificăm doar până la √n
        if (divisor * divisor > n) {
            if (n > 1) {
                factori.push_back({n, 1});
            }
            break;
        }
    }
    return factori;
}

int main() {
    int numar;
    cout << "Introduceti un numar: ";
    cin >> numar;

    if (numar <= 1) {
        cout << "Numarul trebuie sa fie mai mare decat 1!" << endl;
        return 0;
    }

    auto factori = descompuneInFactoriPrimi(numar);

    cout << "Descompunerea in factori primi este: ";
    for (size_t i = 0; i < factori.size(); ++i) {
        cout << factori[i].first << "^" << factori[i].second;
        if (i < factori.size() - 1) {
            cout << " * ";
        }
    }
    cout << endl;

    return 0;
}