Editorial for Number Coloring

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

#include <bits/stdc++.h>
using namespace std;

#define MX (1 << 20)
int P[MX];
int C[MX];
int G[MX];

void init()
{
    iota(P, P + MX, 0);
    for(int i = 2; i < MX; i++)
    {
        if(P[i] == i)
            for(int j = i + i; j < MX; j += i)
                if (P[j] == j)
                    P[j] = i;
        C[i] = 1 + C[i / P[i]]; 
    }
    for(int i: {1, 4, 7, 10, 13})
        G[i] = 1;
    for(int i: {2, 3, 11, 12})
        G[i] = 2;
    for(int i: {5, 6, 8, 9})
        G[i] = 3;
    fill(G + 14, G + 28, 4);
}

int main()
{
    int n;
    cin >> n;
    init();
    int res = 0;
    for(int i = 2; i <= n; i++)
        res = max(res, G[C[i]]);
    cout << res << endl;
    for(int i = 2; i <= n; i++)
        cout << G[C[i]] << ' ';
    cout << endl;
    return 0;
}