307289: CF1333F. Kate and imperfection

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Kate and imperfection

题意翻译

kate有一个集合S,S中的元素是1到n的整数 她认为集合S的一个子集M的集合的不完美值等于 $\max_{a,b\in M} gcd(a,b)$ 且$a!=b$ 对于整数k从2到n,kate想要知道所有大小为k的S的子集中,不完美值最小是多少

题目描述

Kate has a set $ S $ of $ n $ integers $ \{1, \dots, n\} $ . She thinks that imperfection of a subset $ M \subseteq S $ is equal to the maximum of $ gcd(a, b) $ over all pairs $ (a, b) $ such that both $ a $ and $ b $ are in $ M $ and $ a \neq b $ . Kate is a very neat girl and for each $ k \in \{2, \dots, n\} $ she wants to find a subset that has the smallest imperfection among all subsets in $ S $ of size $ k $ . There can be more than one subset with the smallest imperfection and the same size, but you don't need to worry about it. Kate wants to find all the subsets herself, but she needs your help to find the smallest possible imperfection for each size $ k $ , will name it $ I_k $ . Please, help Kate to find $ I_2 $ , $ I_3 $ , ..., $ I_n $ .

输入输出格式

输入格式


The first and only line in the input consists of only one integer $ n $ ( $ 2\le n \le 5 \cdot 10^5 $ ) — the size of the given set $ S $ .

输出格式


Output contains only one line that includes $ n - 1 $ integers: $ I_2 $ , $ I_3 $ , ..., $ I_n $ .

输入输出样例

输入样例 #1

2

输出样例 #1

1

输入样例 #2

3

输出样例 #2

1 1

说明

First sample: answer is 1, because $ gcd(1, 2) = 1 $ . Second sample: there are subsets of $ S $ with sizes $ 2, 3 $ with imperfection equal to 1. For example, $ \{2,3\} $ and $ \{1, 2, 3\} $ .

Input

题意翻译

kate有一个集合S,S中的元素是1到n的整数 她认为集合S的一个子集M的集合的不完美值等于 $\max_{a,b\in M} gcd(a,b)$ 且$a!=b$ 对于整数k从2到n,kate想要知道所有大小为k的S的子集中,不完美值最小是多少

加入题单

算法标签: