#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
const ll mx=1000000;
vector<ll> spf(mx+1);
 
void cspf() {
    for (ll x=2;x<=mx;x++) {
        spf[x] = x;
    }
    for (ll x=2;x*x<=mx;x++) {
        if (spf[x]==x) {
 
            for (ll y=x*x;y<=mx;y+=x) {
                if (spf[y]==y) {
 
                    spf[y]=x;
                }
 
 
            }
        }
    }
}
 
int main() {
    cspf();
    for (ll x=2; x<=20; x++) {
        cout<<"smallest prime factor"<<x<<" :"<<spf[x]<<"\n";
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKCmNvbnN0IGxsIG14PTEwMDAwMDA7CnZlY3RvcjxsbD4gc3BmKG14KzEpOwoKdm9pZCBjc3BmKCkgewogICAgZm9yIChsbCB4PTI7eDw9bXg7eCsrKSB7CiAgICAgICAgc3BmW3hdID0geDsKICAgIH0KICAgIGZvciAobGwgeD0yO3gqeDw9bXg7eCsrKSB7CiAgICAgICAgaWYgKHNwZlt4XT09eCkgewogICAgICAgIAkKICAgICAgICAgICAgZm9yIChsbCB5PXgqeDt5PD1teDt5Kz14KSB7CiAgICAgICAgICAgICAgICBpZiAoc3BmW3ldPT15KSB7CiAgICAgICAgICAgICAgICAJCiAgICAgICAgICAgICAgICAgICAgc3BmW3ldPXg7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgICAgICAJCiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgY3NwZigpOwogICAgZm9yIChsbCB4PTI7IHg8PTIwOyB4KyspIHsKICAgICAgICBjb3V0PDwic21hbGxlc3QgcHJpbWUgZmFjdG9yIjw8eDw8IiA6Ijw8c3BmW3hdPDwiXG4iOwogICAgfQogICAgcmV0dXJuIDA7Cn0=