C - ℕ Coloring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N が与えられます。以下の条件を満たす長さ N の正の整数の列 A_1,A_2,\ldots,A_N であって、数列に現れる値の最大値が最小になるものを一つ出力してください。

  • i が j の約数ならば、A_i \neq A_j (1 \leq i < j \leq N)

制約

  • 1 \leq N \leq 10^5

入力

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

N

出力

数列の各要素を空白で区切って一行に出力せよ。

条件を満たす解が複数存在する場合は、どれを出力してもよい。

A_1 A_2 \ldots A_N

入力例 1

4

出力例 1

1 2 2 3

この出力は以下の条件をすべて満たします。

  • A_1 \neq A_2
  • A_1 \neq A_3
  • A_1 \neq A_4
  • A_2 \neq A_4

また、登場する値の最大値が 2 以下である数列であって、これらの条件をすべて満たすものは存在しないので、この出力は適当です。

Score : 500 points

Problem Statement

Given is an integer N. Among the sequences of N positive integers A_1, A_2, \ldots, A_N satisfying the following condition, print one that minimizes the maximum value in the sequence.

  • If i divides j, A_i \neq A_j (1 \leq i < j \leq N).

Constraints

  • 1 \leq N \leq 10^5

Input

Input is given from Standard Input in the following format:

N

Output

Print a line containing the elements of your sequence, with spaces in between.

If there are multiple valid solutions, any of them will be accepted.

A_1 A_2 \ldots A_N

Sample Input 1

4

Sample Output 1

1 2 2 3

This solution satisfies all of the following conditions:

  • A_1 \neq A_2
  • A_1 \neq A_3
  • A_1 \neq A_4
  • A_2 \neq A_4

Additionally, there is no sequence satisfying these conditions where the maximum value in the sequence is 2 or less, so this is a valid solution.