#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

/**
 * Preveri, ali je dano nenegativno stevilo `n` prastevilo.
 */
bool je_prastevilo(int n) {
    if (n < 2) return false;
    int i = 2;
    while (i*i <= n) {  // se izognemo korenjenju
        if (n % i == 0) {
            return false;
        }
        ++i;
    }
    return true;
}

/**
 * Vrne (neurejen) seznam deliteljev pozitivnega stevila `n`.
 */
vector<int> delitelji(int n) {
    if (n < 1) return {};
    vector<int> del;
    int i = 1;
    while (i*i < n) {
        if (n % i == 0) {  // dodajamo delitelje v parih.
            del.push_back(i);
            del.push_back(n/i);
        }
        ++i;
    }
    if (i*i == n) {  // ce je n popolni kvadrat dodamo zadnjega delitelja samo enkrat.
        del.push_back(i);
    }
    return del;
}

/**
 * Vrne seznam dolzine `n` kjer je na indeksu `i` shranjen
 * shranjen najmanjsi prafaktor stevila `i`.
 *
 * Stevilo `i` je prastevilo, ce velja `sieve[i] == i` in `i != 1`.
 */
vector<int> eratosten(int n) {
    vector<int> sieve(n, 0);
    for (int i = 0; i < n; ++i) sieve[i] = i;
    for (int i = 2; i*i <= n; ++i) {
        if (sieve[i] == i) {  // stevilo `i` se ni precrtano
            for (int j = i*i; j < n; j += i) {  // precrtamo stevila, kjer bi `i` lahko bil najmanjsi veckratnik
                if (sieve[j] == j) {  // ce se nismo nasli nobenega veckratnika
                    sieve[j] = i;  // shranimo `i` kot najmanjsi veckratnik
                }
            }
        }
    }
    return sieve;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    cout << boolalpha;
    int n = 0;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';
    n = 1;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';
    n = 2;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';
    n = 4;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';
    n = 7;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';
    n = 9;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';
    n = 1000000007;
    cout << "je_prastevilo(" << n <<  ") = " << je_prastevilo(n) << '\n';

    n = 1;
    cout << "delitelji(" << n << ") = {"; for (int d : delitelji(n)) cout << d << ", "; cout << "}\n";
    n = 9;
    cout << "delitelji(" << n << ") = {"; for (int d : delitelji(n)) cout << d << ", "; cout << "}\n";
    n = 24;
    cout << "delitelji(" << n << ") = {"; for (int d : delitelji(n)) cout << d << ", "; cout << "}\n";
    n = 1024;
    cout << "delitelji(" << n << ") = {"; for (int d : delitelji(n)) cout << d << ", "; cout << "}\n";

    n = 50;
    cout << "eratosten(" << n << ") = \n";
    auto sieve = eratosten(n);
    for (int i = 0; i < n; ++i) {
        cout << "  " << i << ": " << sieve[i] << '\n';
    }


    return 0;
}