1174C.md (1215B)
1 Source: https://codeforces.com/problemset/problem/1174/C 2 3 C. Ehab and a Special Coloring Problem 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You're given an integer $n$. For every integer $i$ from $2$ to $n$, assign a positive integer $a_i$ such that the following conditions hold: 22 23 * For any pair of integers $(i,j)$, if $i$ and $j$ are coprime, $a_i \neq a_j$. 24 * The maximal value of all $a_i$ should be minimized (that is, as small as possible). 25 26 A pair of integers is called [coprime](https://en.wikipedia.org/wiki/Coprime_integers) if their [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) is $1$. 27 28 Input 29 30 The only line contains the integer $n$ ($2 \le n \le 10^5$). 31 32 Output 33 34 Print $n-1$ integers, $a_2$, $a_3$, $\ldots$, $a_n$ ($1 \leq a_i \leq n$). 35 36 If there are multiple solutions, print any of them. 37 38 Examples 39 40 Input 41 42 ``` 43 4 44 ``` 45 46 Output 47 48 ``` 49 1 2 1 50 ``` 51 52 Input 53 54 ``` 55 3 56 ``` 57 58 Output 59 60 ``` 61 2 1 62 ``` 63 64 Note 65 66 In the first example, notice that $3$ and $4$ are coprime, so $a_3 \neq a_4$. Also, notice that $a=[1,2,3]$ satisfies the first condition, but it's not a correct answer because its maximal value is $3$.