Number Theory |

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) // O(n)
{
    if (n == 1) return 0;
    for (int i = 2; i < n; i++)
    {
        if (n % i == 0) return 0;
    }
    return 1;
}

bool isPrime_sqrt(int n) // O(sqrt(n))
{
    if (n == 1) return 0;
    for (int i = 2; 1ll * i * i <= n; i++)
    {
        if (n % i == 0) return 0;
    }
    return 1;
}

void print_primes_f_1_to_n(int n) // O(n * sqrt(n))
{
    for (int i = 1; i <= n; i++)
    {
        if (isPrime_sqrt(i)) cout << i << ' ';
    }
}

vector<bool> prime;
vector<int> ps;

void sieve(int n) // O(n)
{
    prime.resize(n + 1, 1);
    prime[0] = prime[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (prime[i])
        {
            ps.push_back(i);
            for (int j = i * i; j <= n; j += i)
            {
                prime[j] = 0;
            }
        }
    }
}

void divisores(int n)   // O(n)
{
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0) cout << i << ' ';
    }
}

vector<int> divisores_sqrt(int n)   // O(sqrt(n))
{
    vector<int> dv;
    for (int i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            dv.push_back(i);
            if (i != n / i) dv.push_back(n / i);
        }
    }
    sort(dv.begin(), dv.end());
    return dv;
}

void divisores_f_1_to_n(int n)  // O(n * sqrt(n))
{
    vector<int> dv[n + 1];
    for (int i = 1; i <= n; i++)
    {
        dv[i] = divisores_sqrt(i);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << i << ":\t\t";
        for (auto x : dv[i])
        {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

void divisores_f_1_to_n_sieve(int n)    // O(nlogn)
{
    vector<int> dv[n + 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            dv[j].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << i << ":\t\t";
        for (auto x : dv[i])
        {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

void cnt_divisores_f_1_to_n_sieve(int n)    // O(nlogn)
{
    int cnt_dv[n + 1] {};
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            cnt_dv[j]++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << cnt_dv[i] << ' ';
    }
}

void goldbach(int n)    // O(n)
{
    if (n > 2 && n % 2 == 0)
    {
        sieve(n);
        for (auto p : ps)
        {
            if (prime[n - p])
            {
                cout << p << ' ' << n - p << '\n';
                return;
            }
        }
    }
    else
    {
        cout << "Error\n";
    }
}

vector<pair<int, int>> factorization(int n) // O(sqrt(n))
{
    vector<pair<int, int>> pf;
    for (int i = 2; i * i <= n; i++)
    {
        int e = 0;
        while (n % i == 0)
        {
            n /= i;
            e++;
        }
        if (e) pf.push_back({i, e});
    }
    if (n != 1) pf.push_back({n, 1});
    return pf;
}

int cnt_div_factorization(vector<pair<int, int>> pf)    // O(logn)
{
    int res = 1;
    for (auto [x, y] : pf)
    {
        res *= (y + 1);
    }
    return res;
}

vector<int> lpf;

void get_lpf(int n) // O(n)
{
    lpf.resize(n + 1, 0);
    for (int i = 2; i <= n; i++)
    {
        if (lpf[i] == 0)
        {
            for (int j = i; j <= n; j += i)
            {
                if (lpf[j] == 0) lpf[j] = i;
            }
        }
    }
}

vector<int> factorization_lpf(int n) // O(log n)
{
    vector<int> pf;
    while (n != 1)
    {
        pf.push_back(lpf[n]);
        n /= lpf[n];
    }
    return pf;
}

vector<int> dv;

void generate_dv(int i, vector<pair<int, int>> &pf, int dvv = 1)
{
    if (i == pf.size())
    {
        dv.push_back(dvv);
        return;
    }
    generate_dv(i + 1, pf, dvv);
    for (int j = 0; j < pf[i].second; j++)
    {
        dvv *= pf[i].first;
        generate_dv(i + 1, pf, dvv);
    }
}

int main() {

    int n;
    cin >> n;
    auto pf = factorization(n);
    generate_dv(0, pf);
    sort(dv.begin(), dv.end());
    for (auto x : dv)
    {
        cout << x << ' ';
    }
    return 0;
}