z9.2.cpp

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

// Возвращает список простых множителей числа n
vector<long long> factorize(long long n)
{
    vector<long long> factors;
    for (long long d = 2; d * d <= n; d++)
    {
        while (n % d == 0)
        {
            factors.push_back(d);
            n /= d;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

int main()
{
    long long N;
    cout << "Введите число (<=1e9): ";
    cin >> N;

    vector<long long> f = factorize(N);

    // Формируем красивый вывод: например, 100 -> 2^2 * 5^2
    // Для этого посчитаем кратность каждого множителя
    if (f.empty())
    {
        cout << "Нет множителей (N=0 или 1?)\n";
        return 0;
    }

    // f может быть, например, [2, 2, 5, 5]
    // Сгруппируем
    long long current = f[0];
    int count = 1;
    for (int i = 1; i < (int)f.size(); i++)
    {
        if (f[i] == current)
        {
            count++;
        }
        else
        {
            // Выводим накопленное
            cout << current;
            if (count > 1) cout << "^" << count;
            cout << " * ";
            // Обновляем
            current = f[i];
            count = 1;
        }
    }
    // Выводим последнее
    cout << current;
    if (count > 1) cout << "^" << count;
    cout << endl;

    return 0;
}