201152: [AtCoder]ARC115 C - ℕ Coloring

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

构造一个长度为 $ N $ 的序列 $ A $,对于下标 $ i $, $ j \ (1 \le i < j \le N) \ $,若 $ i $ 为 $ j $ 的因数,$ A_i \neq A_j $。 你需要使这个序列中最大的数尽量小。 输出这个序列。

加入题单

上一题 下一题 算法标签: