#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
const ll MAXN = 1000000;
 
vector<ll> spf(MAXN + 1); // spf[i] will store the smallest prime factor of i
 
void computeSPF() {
    // Initialize spf for every number to itself
    for (ll i = 2; i <= MAXN; i++) {
        spf[i] = i;
    }
 
    // Start the sieve process
    for (ll i = 2; i * i <= MAXN; i++) {
        if (spf[i] == i) { // Check if i is prime
            for (ll j = i * i; j <= MAXN; j += i) {
                if (spf[j] == j) { // Update spf[j] to the smallest prime factor
                    spf[j] = i;
                }
            }
        }
    }
}
 
int main() {
    computeSPF();
    // Example: Print the smallest prime factor for the first 20 numbers
    for (ll i = 2; i <= 20; i++) {
        cout << "Smallest prime factor of " << i << " is " << spf[i] << "\n";
    }
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKCmNvbnN0IGxsIE1BWE4gPSAxMDAwMDAwOwoKdmVjdG9yPGxsPiBzcGYoTUFYTiArIDEpOyAvLyBzcGZbaV0gd2lsbCBzdG9yZSB0aGUgc21hbGxlc3QgcHJpbWUgZmFjdG9yIG9mIGkKCnZvaWQgY29tcHV0ZVNQRigpIHsKICAgIC8vIEluaXRpYWxpemUgc3BmIGZvciBldmVyeSBudW1iZXIgdG8gaXRzZWxmCiAgICBmb3IgKGxsIGkgPSAyOyBpIDw9IE1BWE47IGkrKykgewogICAgICAgIHNwZltpXSA9IGk7CiAgICB9CgogICAgLy8gU3RhcnQgdGhlIHNpZXZlIHByb2Nlc3MKICAgIGZvciAobGwgaSA9IDI7IGkgKiBpIDw9IE1BWE47IGkrKykgewogICAgICAgIGlmIChzcGZbaV0gPT0gaSkgeyAvLyBDaGVjayBpZiBpIGlzIHByaW1lCiAgICAgICAgICAgIGZvciAobGwgaiA9IGkgKiBpOyBqIDw9IE1BWE47IGogKz0gaSkgewogICAgICAgICAgICAgICAgaWYgKHNwZltqXSA9PSBqKSB7IC8vIFVwZGF0ZSBzcGZbal0gdG8gdGhlIHNtYWxsZXN0IHByaW1lIGZhY3RvcgogICAgICAgICAgICAgICAgICAgIHNwZltqXSA9IGk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgY29tcHV0ZVNQRigpOwogICAgLy8gRXhhbXBsZTogUHJpbnQgdGhlIHNtYWxsZXN0IHByaW1lIGZhY3RvciBmb3IgdGhlIGZpcnN0IDIwIG51bWJlcnMKICAgIGZvciAobGwgaSA9IDI7IGkgPD0gMjA7IGkrKykgewogICAgICAgIGNvdXQgPDwgIlNtYWxsZXN0IHByaW1lIGZhY3RvciBvZiAiIDw8IGkgPDwgIiBpcyAiIDw8IHNwZltpXSA8PCAiXG4iOwogICAgfQogICAgcmV0dXJuIDA7Cn0K