#include <iostream>
#include <vector>

using namespace std;

vector<int> delitelji(int n) { // time: O(n)
    vector<int> v;

    /*for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
        }
    }*/
    int i;
    for (i = 1; i*i < n; ++i) {  // O(sqrt(n))
        if (n % i == 0) {
            v.push_back(i);
            v.push_back(n/i);
        }
    }
    if (i*i == n) {  // popolni kvadrat
        v.push_back(i);
    }
    return v;
}

bool je_prastevilo(int n) {
    for (int i = 2; i*i <= n; ++i) {  // O(sqrt(n))
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
// x . . x . x   x x  x    x     x  x  x     x      x x   x    x  x
vector<int> reseto(int n) {  // casovna zahtevnost: ~O(n log(log(n))) ~= O(n)
    vector<int> p(n+1);
    for (int i = 2; i <= n; ++i) p[i] = i;
    for (int i = 2; i <= n; ++i) {
        if (p[i] == i) { // je prastevilo
            for (int64_t j = int64_t(i)*i; j <= n; j += i) {  // pazi na overflow
                p[j] = i;  // shranimo en faktor (lahko spremenimo, da je največji ali najmanjši)
            }
        }
    }
    return p;
}


template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    if (v.empty()) return os << "[]";
    os << "[" << v[0];
    for (size_t i = 1; i < v.size(); ++i) {
        os << ", " << v[i];
    }
    return os << "]";
}

int gcd(int a, int b) {  // najmanjsi veckratnik: a*b / gcd = lcm
    // 144 96
    // 144 = 96 * 1 + ??
    // 96 = ?? * x + &&
    // ?? = ** * x + ..
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    vector<int> d = delitelji(144);
    cout << d << endl;

    cout << reseto(25) << endl;
    vector<int> v = reseto(10000000);
    cout << v[997] << endl;

    int b = 8763245;
    cout << "Faktorji " << b << ": ";
    while (v[b] != b) {
        cout << v[b] << ", ";
        b /= v[b];
    }
    cout << b << endl;

    cout << gcd(-144, 96) << endl;

   return 0;
}