#P1174C. Ehab and a Special Coloring Problem
Ehab and a Special Coloring Problem
Description
You're given an integer $n$. For every integer $i$ from $2$ to $n$, assign a positive integer $a_i$ such that the following conditions hold:
- For any pair of integers $(i,j)$, if $i$ and $j$ are coprime, $a_i \neq a_j$.
- The maximal value of all $a_i$ should be minimized (that is, as small as possible).
A pair of integers is called coprime if their greatest common divisor is $1$.
The only line contains the integer $n$ ($2 \le n \le 10^5$).
Print $n-1$ integers, $a_2$, $a_3$, $\ldots$, $a_n$ ($1 \leq a_i \leq n$).
If there are multiple solutions, print any of them.
Input
The only line contains the integer $n$ ($2 \le n \le 10^5$).
Output
Print $n-1$ integers, $a_2$, $a_3$, $\ldots$, $a_n$ ($1 \leq a_i \leq n$).
If there are multiple solutions, print any of them.
Samples
4
1 2 1
3
2 1
Note
In the first example, notice that $3$ and $4$ are coprime, so $a_3 \neq a_4$. Also, notice that $a=[1,2,3]$ satisfies the first condition, but it's not a correct answer because its maximal value is $3$.