codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.