Number theory

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <deque>
#include <math.h>
#include <iomanip>
#define pb push_back
#define int long long
using namespace std;

const int N = 2e5 + 5;
const int M = 1e9 + 7;

///O(log N), every second step we divide n by 2
//pow(12, 2), 143.999999999 -> 143
//pow(a, n);
int binpow(int a, int n) {
    if (n == 0) return 1;
    if (n % 2 == 1) return binpow(a, n - 1) * a % M;
    int x = binpow(a, n / 2);
    return x * x % M;
}

int binpowNonRec(int a, int n) {
    int res = 1;
    ///0 --- false
    ///!=0 --- true
    ///How it works: look at binary representation of n
    while (n) ///while (n != 0)
        if (n % 2) {///if (n % 2 != 0)
            res *= a;
            res %= M;
            n--;
        } else {
            a *= a;
            a %= M;
            n /= 2;
        }
    return res;
}

///how many divisors are there? O(cubic root of n) = O(n^(1/3))
///O(sqrt(N))
vector<int> findDivisors(int n) {
    vector<int> res;
    for (int a = 1; a * a <= n; a++)
        if (n % a == 0) {
            res.push_back(a);
            if (n / a != a)
                res.push_back(n / a);
        }
    sort(res.begin(), res.end());
    return res;
}

bool isPrime(int n) {
    if (n == 1) return 0;
    for (int a = 2; a * a <= n; a++)
        if (n % a == 0)
            return 0;
    return 1;
}

vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> res;
    for (int p = 2; p * p <= n; p++)
        if (n % p == 0) {
            int a = 0;
            while (n % p == 0) {
                n /= p;
                a++;
            }
            res.push_back({p, a});
        }
    if (n != 1)
        res.push_back({n, 1});
    return res;
}

//O(log MAX)
int gcd(int a, int b) {
    /*
    if (a == 0)
        return b;
    if (b == 0)
        return a;*/
    if (a == 0 || b == 0)
        return a + b;
    if (a <= b)
        return gcd(a, b % a);
    else
        return gcd(a % b, b);
}


///O(N log log N) ---> O(N)
///factorize the numbers
///marked[i] = not 0/1, but the smallest divisor of i
vector<int> sieve(int N) {
    vector<int> marked(N + 1);
    ///bitset --- C++ builtin structure
    vector<int> primes;
    for (int i = 2; i <= N; i++)
        if (!marked[i]) {
            marked[i] = i; ///i is prime, so the smallest divisor of i is i
            primes.push_back(i);
            for (long long j = i; j * i <= N; j++)
                if (marked[j * i] == 0)
                    marked[j * i] = i;
        }
    return marked;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //cout << binpow(102, 2103019) << ' ' << binpowNonRec(102, 2103019);
    /*vector<int> d = findDivisors(16);
    for (auto div : d)
        cout << div << ' ';*/

    /*
    vector<pair<int, int>> fact = factorize(1000000007);
    ///fact.size() is very small, even smaller than logarithm
    for (auto [p, a] : fact) {
        cout << p << ' ' << a << "\n";
    }*/

    //cout << gcd(13, 37) << ' ' << gcd(12, 15) << ' ' << __gcd(13, 37);
    /*vector<int> p = sieve(100);
    for (auto pr : p)
        cout << pr << ' ';
*/
/// a lot of relatively small numbers -- it's fine.
    vector<int> d = sieve(1000);
    int x = 124;
    while (x != 1) {
        cout << d[x] << ' '; ///smallest divisor of x
        x = x / d[x];
    }
    return 0;
}