← 返回题目列表

Codeforces · 1333/F

F. 凯特和不完美

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

Kate 有一组 $$$S$$$ 的 $$$n$$$ 整数 $$$\{1, \dots, n\} $$$。

她认为子集 $$$M \subseteq S$$$ 的缺陷等于所有对 $$$(a, b)$$$ 上 $$$gcd(a, b)$$$ 的最大值,使得 $$$a$$$ 和 $$$b$$$ 都在 $$$M$$$ 和 $$$a \neq b$$$ 中。

Kate 是一个非常整洁的女孩,对于每个 $$$k \in \{2, \dots, n\}$$$,她希望找到一个子集,该子集是 $$$S$$$ 中大小为 $$$k$$$ 的所有子集中缺陷最小的子集。可能存在多个具有最小缺陷和相同尺寸的子集,但您无需担心这一点。凯特想要自己找到所有子集,但她需要您的帮助来找到每个尺寸 $$$k$$$ 的最小可能缺陷,将其命名为 $$$I_k$$$。

请帮助 Kate 找到 $$$I_2$$$、$$$I_3$$$、...、$$$I_n$$$。

输入

输入中的第一行也是唯一一行仅包含一个整数 $$$n$$$ ($$$2\le n \le 5 \cdot 10^5$$$) — 给定集合 $$$S$$$ 的大小。

输出

输出仅包含一行,其中包括 $$$n - 1$$$ 整数:$$$I_2$$$、$$$I_3$$$、...、$$$I_n$$$。

示例

输入 #1

2

输出 #1

1

输入 #2

3

输出 #2

1 1

注意

第一个示例:答案是 1,因为 $$$gcd(1, 2) = 1$$$。

第二个样本:存在 $$$S$$$ 的子集,其大小为 $$$2, 3$$$,不完美度等于 1。例如,$$$\{2,3\}$$$ 和 $$$\{1, 2, 3\}$$$。