Ehab and a Special Coloring Problem
题意翻译
你有一个数组,长度为n,现在你需要构造一个序列,使得这个序列满足如下要求:
* 对于任意一对$i,j$,如果$\gcd(i,j)=1$,则$a[i]!=a[j]$
* 使该序列中的最大值最小化。
请输出这个序列的第二个位置到最后一个位置的值。
题目描述
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](https://en.wikipedia.org/wiki/Coprime_integers) if their [greatest common divisor](https://en.wikipedia.org/wiki/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.
输入输出样例
输入样例 #1
4
输出样例 #1
1 2 1
输入样例 #2
3
输出样例 #2
2 1
说明
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 $ .