1. Concise Problem Statement  
Given an integer N (1 ≤ N ≤ 2^20), assign to each integer i in [1..N] a “color” c[i] (an integer in [1..M]) so that whenever A is divisible by B (A ≠ B), c[A] ≠ c[B]. Minimize the number of colors M used. Output M on the first line and any valid coloring c[1..N] on the second line.

2. Detailed Editorial  

  A. Reformulation as a graph‐coloring problem  
  Define a graph G with vertices {1,2,…,N} and an edge between any two numbers A, B if one divides the other. We seek a proper vertex coloring of G using the fewest colors.  

  B. Perfectness and chain‐decomposition  
  The divisibility relation is a partial order; its comparability graph is a perfect graph. By Dilworth’s theorem (and properties of perfect graphs), the chromatic number equals the size of the largest clique in G, which for a comparability graph is the length of the longest chain under divisibility.  

  C. Characterizing the longest divisor‐chain  
  A “divisor chain” is a sequence 1 = d_0 < d_1 < … < d_k ≤ N where each d_{i+1} is a multiple of d_i. To maximize k+1, you would at each step multiply by the smallest prime possible—so the longest chain up to N is  
    1 → 2 → 2^2 → … → 2^k   with 2^k ≤ N < 2^{k+1}.  
  Hence the minimum number of colors M = k+1 = ⌊log₂N⌋ + 1.  

  D. Constructing an optimal coloring  
  It suffices to assign to each i the length of the longest divisor‐chain ending at i (this is a standard DP/mex‐based greedy coloring):  
    dp[i] = 1 + max{ dp[d] : d | i, d < i }.  
  Then dp[1] = 1, and finally M = max_i dp[i], with c[i] = dp[i].  

  E. Efficient implementation  
  1. Sieve‐like DP in O(N log N):  
     - Initialize dp[i] = 1 for all i.  
     - For i from 1 to N: for each multiple j = 2i, 3i, … ≤ N, do dp[j] = max(dp[j], dp[i] + 1).  
  2. Or, even faster in O(N log log N), compute the total number of prime factors (with multiplicity) Ω(i) via a smallest‐prime‐factor sieve, then observe dp[i] = Ω(i) + 1.  

  Both approaches produce an optimal M and a valid coloring in time well within the limits.  

3. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;

void read() { cin >> n; }

void solve() {
    // Build the divisibility DAG: every proper divisor of i is a neighbour of
    // i. A valid painting needs different colors for any A divisible by B, so
    // the chromatic requirement is exactly a graph coloring on this DAG.
    //
    // Process numbers in increasing order and greedily assign each i the
    // smallest color not used by its (already colored) divisors. The number of
    // colors equals the length of the longest divisor chain, i.e. one plus the
    // number of prime factors counted with multiplicity, which is optimal.

    vector<int> answer(n + 1, 1);
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = i * 2; j <= n; j += i) {
            adj[j].push_back(i);
        }
    }

    vector<char> used(n + 2, 0);
    for(int i = 1; i <= n; i++) {
        for(int v: adj[i]) {
            used[answer[v]] = 1;
        }
        while(used[answer[i]]) {
            answer[i]++;
        }
        for(int v: adj[i]) {
            used[answer[v]] = 0;
        }
    }

    int mx_col = 1;
    for(int i = 1; i <= n; i++) {
        mx_col = max(mx_col, answer[i]);
    }

    cout << mx_col << '\n';
    for(int i = 1; i <= n; i++) {
        cout << answer[i] << " ";
    }
    cout << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution with Detailed Comments  
```python
import sys
sys.setrecursionlimit(10**7)

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])

    # We'll compute Ω[i] = number of prime factors of i (with multiplicity)
    # using a sieve for the smallest prime factor (spf).
    spf = [0] * (n+1)
    Omega = [0] * (n+1)
    # Standard sieve to fill spf[i] = smallest prime dividing i
    for i in range(2, n+1):
        if spf[i] == 0:  # i is prime
            for j in range(i, n+1, i):
                if spf[j] == 0:
                    spf[j] = i
    # Now compute Omega[i] = Omega[i//spf[i]] + 1
    for i in range(2, n+1):
        Omega[i] = Omega[i // spf[i]] + 1
    # Our coloring dp[i] = Omega[i] + 1
    dp = [Omega[i] + 1 for i in range(n+1)]
    # The number of colors needed is max dp[i]
    M = max(dp[1:])
    # Output
    out = []
    out.append(str(M))
    out.append(" ".join(str(dp[i]) for i in range(1, n+1)))
    print("\n".join(out))

if __name__ == "__main__":
    main()
```

5. Compressed Editorial  
Use the fact that the divisibility graph on {1..N} is perfect, so its chromatic number equals the size of its largest chain under divisibility. The maximum chain is 1→2→4→…→2^k with 2^k≤N, so M=⌊log₂N⌋+1. Color each i by the length of the longest chain ending at i, computable either via a sieve‐style DP in O(N log N) or by computing Ω(i) (total prime‐factor count) in O(N log log N), since dp[i]=Ω(i)+1.