C - Coprime Set 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

正の整数 N が与えられます。整数列 A = (A_1, A_2, \ldots, A_N) であって、次の条件をすべて満たすものをひとつ出力してください。

  • 1\leq A_i\leq 10000
  • i\neq j に対して、A_i\neq A_j かつ \gcd(A_i, A_j) > 1
  • \gcd(A_1, A_2, \ldots, A_N) = 1

なお、この問題の制約のもとで、条件を満たす整数列が存在することが証明できます。

制約

  • 3\leq N\leq 2500

入力

入力は以下の形式で標準入力から与えられます。

N

出力

条件を満たす整数列 A の各要素を、空白で区切って 1 行で出力してください。

A_1 A_2 \ldots A_N

条件を満たす整数列が複数存在する場合は、どれを出力しても正解となります。

入力例 1

4

出力例 1

84 60 105 70
  • \gcd(84,60) = 12
  • \gcd(84,105) = 21
  • \gcd(84,70) = 14
  • \gcd(60,105) = 15
  • \gcd(60,70) = 10
  • \gcd(105,70) = 35
  • \gcd(84,60,105,70) = 1

が成り立ち、すべての条件が満たされていることが確認できます。

Score : 500 points

Problem Statement

Given is a positive integer N. Print an integer sequence A = (A_1, A_2, \ldots, A_N) satisfying all of the following:

  • 1\leq A_i\leq 10000;
  • A_i\neq A_j and \gcd(A_i, A_j) > 1 for i\neq j;
  • \gcd(A_1, A_2, \ldots, A_N) = 1.

We can prove that, under the Constraints of this problem, such an integer sequence always exists.

Constraints

  • 3\leq N\leq 2500

Input

Input is given from Standard Input in the following format:

N

Output

Print the elements in your integer sequence A satisfying the conditions in one line, with spaces in between.

A_1 A_2 \ldots A_N

If multiple sequences satisfy the conditions, any of them will be accepted.

Sample Input 1

4

Sample Output 1

84 60 105 70

All of the conditions are satisfied, since we have:

  • \gcd(84,60) = 12
  • \gcd(84,105) = 21
  • \gcd(84,70) = 14
  • \gcd(60,105) = 15
  • \gcd(60,70) = 10
  • \gcd(105,70) = 35
  • \gcd(84,60,105,70) = 1