D - Five, Five Everywhere Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点：400 点

問題文

以下の条件を満たす, 長さ N の数列 a_1, a_2, ..., a_N を 1 つ出力してください.

  • a_i \ (1 \leq i \leq N) は 55 \ 555 以下の素数である.
  • a_1, a_2, ..., a_N の値はすべて異なる.
  • a_1, a_2, ..., a_N からどの異なる 5 個の整数を選んでも, この合計は合成数になる.

条件を満たす数列が複数個存在するとき、条件を満たすもののうちどのような数列を出力しても正解となります.

備考

2 以上の整数 N が, 1 と N 以外のどの正の整数でも割り切れなければ N は「素数」であり, そうでない場合 N は「合成数」である.

制約

  • N は 5 以上 55 以下の整数

入力

入力は以下の形式で標準入力から与えられる. 

N

出力

1 行に, N 個の数 a_1, a_2, a_3, ..., a_N を空白区切りで出力しなさい.

入力例 1

5

出力例 1

3 5 7 11 31

まず, 3, 5, 7, 11, 31 は全て異なり, 全て素数です.
これらから 5 個の整数を選ぶ方法は, 「全てを選ぶ」の 1 通りのみです. a_1+a_2+a_3+a_4+a_5=57 であり, この値は合成数なので問題文の条件を満たします.
他にも, 2 3 5 7 13 11 13 17 19 31 7 11 5 31 3 などを出力しても正解となります.

入力例 2

6

出力例 2

2 3 5 7 11 13
  • 2, 3, 5, 7, 11, 13 は全て異なる素数です.
  • 2+3+5+7+11=28 であり, 合成数です.
  • 2+3+5+7+13=30 であり, 合成数です.
  • 2+3+5+11+13=34 であり, 合成数です.
  • 2+3+7+11+13=36 であり, 合成数です.
  • 2+5+7+11+13=38 であり, 合成数です.
  • 3+5+7+11+13=39 であり, 合成数です.

よって, 2 3 5 7 11 13 は条件を満たす数列です.

入力例 3

8

出力例 3

2 5 7 13 19 37 67 79

Score: 400 points

Problem Statement

Print a sequence a_1, a_2, ..., a_N whose length is N that satisfies the following conditions:

  • a_i (1 \leq i \leq N) is a prime number at most 55 555.
  • The values of a_1, a_2, ..., a_N are all different.
  • In every choice of five different integers from a_1, a_2, ..., a_N, the sum of those integers is a composite number.

If there are multiple such sequences, printing any of them is accepted.

Notes

An integer N not less than 2 is called a prime number if it cannot be divided evenly by any integers except 1 and N, and called a composite number otherwise.

Constraints

  • N is an integer between 5 and 55 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print N numbers a_1, a_2, a_3, ..., a_N in a line, with spaces in between.

Sample Input 1

5

Sample Output 1

3 5 7 11 31

Let us see if this output actually satisfies the conditions.
First, 3, 5, 7, 11 and 31 are all different, and all of them are prime numbers.
The only way to choose five among them is to choose all of them, whose sum is a_1+a_2+a_3+a_4+a_5=57, which is a composite number.
There are also other possible outputs, such as 2 3 5 7 13, 11 13 17 19 31 and 7 11 5 31 3.

Sample Input 2

6

Sample Output 2

2 3 5 7 11 13
  • 2, 3, 5, 7, 11, 13 are all different prime numbers.
  • 2+3+5+7+11=28 is a composite number.
  • 2+3+5+7+13=30 is a composite number.
  • 2+3+5+11+13=34 is a composite number.
  • 2+3+7+11+13=36 is a composite number.
  • 2+5+7+11+13=38 is a composite number.
  • 3+5+7+11+13=39 is a composite number.

Thus, the sequence 2 3 5 7 11 13 satisfies the conditions.

Sample Input 3

8

Sample Output 3

2 5 7 13 19 37 67 79