лаба 11

#include "bits/stdc++.h"
//speed coding handle

#define mp make_pair
#define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " ";  }cout << "\n";} ;
#define f first
#define s second
#define loop(i, x, n) for (int i = x; i < n; i++)
#define joop(x, n) for (ll j = x; j < n; j++)
#define lp(n) for (ll i = 0; i < n; i++)
#define err cout << "ERROR" << endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) x.size()
#define rndm rng()

// types
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
typedef long long ll;
typedef long double ld;

// types of data
#define inf 1000000000
#define infll 1000000000000000000
#define INF ll(1e18)

#define md 998244353
#define mod 1000000009
//#define K 239017

#define DEBUG 1
using namespace std;
mt19937_64 rng(113113);
uniform_int_distribution<ll> drist;

// code


struct bignumber // описание узла
{
    short digit; // цифра
    bignumber* next; // поле для связи со следующей цифрой числа
};
bignumber* create(string str) // создание большого числа из текстовой строки
{
    bignumber* p, * top = nullptr;
    int i;
    for (i = 0; i < str.size() ; i++)
    {
        p = new bignumber;
        p->digit = short(str[i]) - short('0');
        p->next = top;
        top = p;
    }
    return top;
}
void print(const bignumber* BigNum) // рекурсивная распечатка цифр числа
{
    if (BigNum != nullptr) // если ещё не конец числа
    {
        print(BigNum->next); //вызываем печать для старшего разряда
        cout << BigNum->digit; //печать текущего разряда
    }
}
void clear(bignumber** BigNum) // очистка стека (удаление всех узлов из стека)
{
    bignumber* temp;
    while (*BigNum != nullptr) // пока не достигли конца
    {
        temp = (*BigNum)->next; // устанавливаем указатель temp на следующий элемент
        delete* BigNum;
        *BigNum = temp; // переводим указатель на следующий элемент
    }
}

int dlina(bignumber* BigNum)
{
    int k = 0;
    while (BigNum != nullptr)
    {
        k++;
        BigNum = BigNum->next;
    }
    return k;
}


bool Eq(bignumber* BigNum1, bignumber* BigNum2) //проверка, что BigNum1=BigNum2
{
    if (dlina(BigNum1) != dlina(BigNum2)) return false;
    else //если одинаковое число разрядов
    {
        bool fl = true;
        while (BigNum1 != nullptr)//проверяем совпадение цифр
        {
            if (BigNum1->digit != BigNum2->digit) { fl = false; break; }
            BigNum1 = BigNum1->next;
            BigNum2 = BigNum2->next;
        }
        return fl;
    }
}
int sravn(bignumber* BigNum1, bignumber* BigNum2)
{//если равное число разрядов, сравниваем цифры
    if (BigNum1 == nullptr) return 0;
    else
    {
        int k = sravn(BigNum1->next, BigNum2->next);
        if (k != 0) return k;
        else //k=0, старшие разряды были одинаковые
            return BigNum1->digit - BigNum2->digit;
    }
}


bool More(bignumber* BigNum1, bignumber* BigNum2) //BigNum1>BigNum2
{
    int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
    if (d1 < d2) return false;
    if (d1 > d2) return true;
    //если одинаковое число разрядов
    int k = sravn(BigNum1, BigNum2);
    if (k > 0) return true;
    return false;
}

bool Less(bignumber* BigNum1, bignumber* BigNum2) //BigNum1<BigNum2
{
    int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
    if (d1 < d2) return true;
    if (d1 > d2) return false;
    //если одинаковое число разрядов
    int k = sravn(BigNum1, BigNum2);
    if (k < 0) return true;
    return false;
}

bool LessEq(bignumber* BigNum1, bignumber* BigNum2) //BigNum1<=BigNum2
{
    int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
    if (d1 < d2) return true;
    if (d1 > d2) return false;
    //если одинаковое число разрядов
    int k = sravn(BigNum1, BigNum2);
    if (k <= 0) return true;
    return false;
}
bool MoreEq(bignumber* BigNum1, bignumber* BigNum2) //BigNum1>BigNum2
{
    int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
    if (d1 < d2) return false;
    if (d1 > d2) return true;
    //если одинаковое число разрядов
    int k = sravn(BigNum1, BigNum2);
    if (k >= 0) return true;
    return false;
}

void addto(bignumber** BigNum1, bignumber* BigNum2)
{//сложение двух больших чисел с накапливанием в первое
    if (!BigNum2) return;
    short digit = 0, carry = 0;
    bignumber* prev = *BigNum1, * temp = *BigNum1;
    bignumber* p = nullptr;
    while ((temp != nullptr))
    {
        //учитываем перенос
        digit = carry;
        if (BigNum2 != nullptr) {
            digit = digit + BigNum2->digit;
            BigNum2 = BigNum2->next; //переходим к следующей цифре 2 числа
        }
        if (temp != nullptr) {
            digit = digit + temp->digit;
            prev = temp;
            temp = temp->next;
        }
        //вычисляем новый перенос
        carry = digit / 10;
        //вычисляем цифру текущего разряда
        digit = digit % 10;
        prev->digit = digit;
    }
    while ((carry > 0) || (BigNum2 != nullptr))//создаем новые разряды в 1 числе
    {
        digit = carry;
        if (BigNum2 != nullptr) {
            digit = digit + BigNum2->digit;
            BigNum2 = BigNum2->next; //переходим к следующей цифре 2 числа
        }
        //вычисляем новый перенос
        carry = digit / 10;
        //вычисляем цифру текущего разряда
        digit = digit % 10;
        p = new bignumber;
        p->digit = digit;
        p->next = nullptr;
        if (prev != nullptr) {//был предшествующий узел
            prev->next = p;
        }
        else {
            if (*BigNum1 == nullptr) *BigNum1 = p;
        }
        prev = p;

    }

}

void subtract(bignumber** BigNum1, bignumber* BigNum2)
{
    if (!BigNum2) return;
    short digit = 0, borrow = 0;
    bignumber* prev = *BigNum1, * temp = *BigNum1;
    bignumber* p = nullptr;
    while (temp != nullptr)
    {
        // Учитываем заем
        digit = borrow + temp->digit;
        if (BigNum2 != nullptr) {
            digit -= BigNum2->digit;
            BigNum2 = BigNum2->next; // Переходим к следующей цифре второго числа
        }
        // Вычисляем новый заем
        borrow = digit < 0 ? -1 : 0;
        // Вычисляем цифру текущего разряда
        digit = (digit + 10) % 10;
        prev->digit = digit;
        temp = temp->next;
        prev = temp;
    }
}

bignumber* Mult(bignumber* BigNum, int N, int carry)
{
    int digit = carry;//прибавляем перенос
    bignumber* p = nullptr;
    if ((carry != 0) || (BigNum != nullptr))
    {
        if (BigNum != nullptr)
        { //умножаем цифру числа на N
            digit = digit + N * (BigNum->digit);
            //переходим к следующей цифре
            BigNum = BigNum->next;
        }
        //вычисляем новый перенос
        carry = digit / 10;
        //вычисляем цифру текущего разряда
        digit = digit % 10;
        //создаем этот разряд
        p = new bignumber;
        p->digit = digit;
        //остальные разряды вычисляем рекурсивно
        p->next = Mult(BigNum, N, carry);
    }
    return p;
}
void shift(bignumber** BigNum, int n) //поразрядный сдвиг на n (домножение на 10^n)
{
    bignumber* temp = *BigNum;
    int i;
    for (i = 0; i < n; i++)
    {
        //создаем новый разряд
        temp = new bignumber;
        temp->digit = 0;
        //подцепляем предыдущие разряды
        temp->next = *BigNum;
        *BigNum = temp;
    }
}
bignumber* BigMult(bignumber* BigNum1, bignumber* BigNum2)
{
    bignumber* p = nullptr, * temp = nullptr;
    if (BigNum1 != nullptr)
    {
        int k = 0; //сдвиг разрядов при умножении
        p = new bignumber;
        p->digit = 0;
        p->next = nullptr;
        while (BigNum2 != nullptr)
        {
            temp = Mult(BigNum1, BigNum2->digit, 0);//умножение 1-го числа на текущую цифру 2го

            shift(&temp, k);
            addto(&p, temp);
            clear(&temp);
            temp = nullptr;
            BigNum2 = BigNum2->next;
            k++;
        }
    }
    return p;
}

// с округлением вниз
bignumber* div(bignumber* sa, bignumber *ba){ // a - b * k = 0 <=> a = bk
    bignumber *zero, *bi, *one, *a, *b;
    a = create("1");
    b = create("1");
    a = BigMult(a, sa);
    b = BigMult(b, ba);
    // скопировал
    zero = create("0");
    bi = create("0");
    one = create("1");
    while(More(a, zero)){ // while(a > 0) / while(a > b) <=>
        addto(&zero, b);
        addto(&bi, one);
    }
//    cout << "xueta:";
//    print(bi);
//    cout << endl;
    return bi;
}

void solve(){
    string n = "128";

    cin >> n;
    bignumber *bn, *bi, *bd, *one;
    bn = create(n);
    bi = create("2");
    one = create("1");
    while(More(bn, one)){ // n >= 1
        bignumber *divider;

        divider = div(bn, bi);
        while(Eq(BigMult(divider, bi ), bn)){ // если делится нацело

            divider = div(bn, bi); // частное bn/bi с округлением вниз

            print(bi); // простой делитель
            cout << "\n";
            bn = divider; // разложил
            divider = div(bn, bi); // для проверки, делится ли то, которое сейчас
        }
        addto(&bi, one); // смиотрим некст
        clear(&divider);
    }
    clear(&bn); clear(&bi); clear(&bd); clear(&one);

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
//    freopen("text.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    solve();
    return 1;
}