z9.3.cpp

#include <iostream>
#include <cmath>
#include "string.h"
#include "array.h"
using namespace std;

Array<long long> factorize(long long n)
{
    Array<long long> arr;
    for (long long d = 2; d * d <= n; d++)
    {
        while (n % d == 0)
        {
            arr.append(d);
            n /= d;
        }
    }
    if (n > 1)
    {
        arr.append(n);
    }
    return arr;
}

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

    Array<long long> factors = factorize(N);

    if (factors.size() == 0)
    {
        cout << "Число " << N << " не имеет простых множителей (возможно это 1?)\n";
        return 0;
    }

    // Оформим вывод в виде строки, например "2^2 * 5^2"
    String output;
    long long currentFactor = factors[0];
    int count = 1;
    for (int i = 1; i < factors.size(); i++)
    {
        if (factors[i] == currentFactor)
        {
            count++;
        }
        else
        {
            // Добавим к output
            String part = to_string(currentFactor).c_str();
            if (count > 1)
            {
                part = part + "^";
                part = part + to_string(count).c_str();
            }
            // Если вывод уже не пуст, добавим " * "
            if (output.length() > 0)
            {
                output = output + " * ";
            }
            output = output + part;

            // Обновим
            currentFactor = factors[i];
            count = 1;
        }
    }
    // Не забыть последнее "скопившееся"
    {
        String part = to_string(currentFactor).c_str();
        if (count > 1)
        {
            part = part + "^";
            part = part + to_string(count).c_str();
        }
        if (output.length() > 0) output = output + " * ";
        output = output + part;
    }

    cout << "Разложение: " << output << endl;

    return 0;
}