Coloring Natural Numbers

Time limit1sMemory limit1024 MB

Summary

Assign colors to 1..N so coprime numbers differ, using the minimum possible number of colors, and output the count and a valid coloring.

Level: Medium7 of 10
Topics: Number theory, Math, Greedy, Combinatorics
Solved: No attempts yet

Problem

Color the natural numbers from $1$ to $N$ . Two distinct coprime natural numbers must receive different colors. Write a program that finds a way to color all the numbers using the minimum number of colors.

Input

The first line gives the natural number $N$ . ( $1 \le N \le 500\,000$ )

Output

On the first line, print the number of colors used, $K$ .

On the second line, print $N$ numbers separated by spaces. The $i$ -th number is the color of the natural number $i$ . Colors are integers from $1$ to $K$ .

Hint

The following are examples of a valid coloring and an invalid coloring for $N=5$ .

The first coloring is a valid coloring. Although $2$ and $4$ are colored the same, they are not coprime, so the condition of the problem is not violated. One can also prove that at least $4$ colors are needed to color the natural numbers up to $5$ .

The second coloring is an invalid coloring because the coprime numbers $2$ and $3$ are colored the same.

The third coloring is an invalid coloring because it does not use the minimum number of colors.

Examples1

Example 1
Input
```
5
```
Expected output
```
4
1 2 3 2 4
```