← 返回题目列表

Codeforces · 1174/C

C. Ehab 和特殊的着色问题

中文机器翻译题面 查看原题

给你一个整数$$$n$$$。对于从 $$$2$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,分配一个正整数 $$$a_i$$$,使得以下条件成立:

- 对于任何整数对 $$$(i,j)$$$,如果 $$$i$$$ 和 $$$j$$$ 互质,则 $$$a_i \neq a_j$$$。
- 所有 $$$a_i$$$ 的最大值应最小化(即尽可能小)。

如果一对整数的最大公约数为 $$$1$$$,则称为互质。

输入

唯一一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

输出

打印 $$$n-1$$$ 整数、$$$a_2$$$、$$$a_3$$$、$$$\ldots$$$、$$$a_n$$$ ($$$1 \leq a_i \leq n$$$)。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4

输出 #1

1 2 1

输入 #2

3

输出 #2

2 1

注意

在第一个示例中,请注意 $$$3$$$ 和 $$$4$$$ 互质,因此 $$$a_3 \neq a_4$$$。另外,请注意 $$$a=[1,2,3]$$$ 满足第一个条件,但这不是正确答案,因为它的最大值是 $$$3$$$。