Ehab and a Special Coloring Problem

1000ms

262144K

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$$$.

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.

Sample Input:

Sample Output:

1 2 1

Sample Input:

Sample Output:

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$$$.

Informação

Provedor Codeforces

Código CF1174C