/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 N が与えられます。1 以上 N 以下の正整数からなる集合 S であって、以下の条件を満たすものを良い集合といいます。
- 任意の S の要素 x,y に対して、x を y で割った余りは 1 ではない。
要素数が最大である良い集合を一つ構築してください。
制約
- 1 \le N \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N
出力
あなたの構築した良い集合 S の要素数を k、要素を S = \lbrace S_1,S_2,\dots,S_k \rbrace としたとき、以下のように出力せよ。
k S_1\ S_2\ \dots\ S_k
答えが複数ある場合は、そのどれを出力しても正解になる。
入力例 1
5
出力例 1
2 3 5
例えば、\lbrace 3,5 \rbrace や \lbrace 2 \rbrace は良い集合です。逆に、\lbrace 2,3,5 \rbrace や \lbrace 1,2,3,4,5 \rbrace は良い集合ではありません。
要素数が 3 以上の良い集合は存在しないため、\lbrace 3,5 \rbrace は要素数が最大である良い集合の一つです。
入力例 2
2
出力例 2
1 2
Score : 300 points
Problem Statement
You are given a positive integer N. A set S of positive integers between 1 and N (inclusive) is called a good set if it satisfies the following condition:
- For every pair of elements x and y in S, the remainder when x is divided by y is not 1.
Construct one good set with the maximum possible number of elements.
Constraints
- 1 \le N \le 2 \times 10^{5}
Input
The input is given from Standard Input in the following format:
N
Output
Let k be the number of elements of the good set S you constructed, and let S = \lbrace S_1,S_2,\dots,S_k \rbrace be its elements. Output in the following format:
k S_1\ S_2\ \dots\ S_k
If multiple solutions exist, any of them will be accepted.
Sample Input 1
5
Sample Output 1
2 3 5
For example, \lbrace 3,5 \rbrace and \lbrace 2 \rbrace are good sets. On the other hand, \lbrace 2,3,5 \rbrace and \lbrace 1,2,3,4,5 \rbrace are not good sets.
No good set with three or more elements exists, so \lbrace 3,5 \rbrace is one of the good sets with the maximum number of elements.
Sample Input 2
2
Sample Output 2
1 2