Sherlock and his girlfriend

题意翻译

### 题目描述 Sherlock 有一个新女朋友。现在情人节就要到了，他想送给她一些珠宝。 他买了几件首饰。第 $i$ 件的价格等于 $i+ 1$，也就是说，珠宝的价格分别为 $2,3,4,n + 1$ 。 现在需要给这些珠宝首饰上色。**当一件珠宝的价格是另一件珠宝的价格的素因子时，这两件的颜色就不允许相同。** 此外，要最少化使用的颜色数量。 ### 输入输出格式： #### 输入格式： 一行，包含单个整数 $n(1\le n\leq 100000)$ 指珠宝的数量。 ### 输出格式 第一行的输出包含一个整数 $K$，指最少颜色的颜色种类数。 第二行由 $n$ 个整数（$1$ 到 $k$）组成，按价格从小到大来表示每件珠宝的颜色。 如果有多种方法，则可以输出它们中的任何一种。 ### 说明与提示 在第一个样例中，第一、第二和第三件首饰的价格分别为 $2$、$3$、$4$,它们的颜色分别为 $1$ 、$1$ 和 $2$。 在这种情况下，由于 $2$ 是 $4$ 的因子，所以具有因数 $2$ 和 $4$ 的珠宝的颜色必须是不同的。 Translated by @皎月半洒花。

题目描述

Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry. He bought $ n $ pieces of jewelry. The $ i $ -th piece has price equal to $ i+1 $ , that is, the prices of the jewelry are $ 2,3,4,...\ n+1 $ . Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used. Help Sherlock complete this trivial task.

输入输出格式

输入格式

The only line contains single integer $ n $ ( $ 1<=n<=100000 $ ) — the number of jewelry pieces.

输出格式

The first line of output should contain a single integer $ k $ , the minimum number of colors that can be used to color the pieces of jewelry with the given constraints. The next line should consist of $ n $ space-separated integers (between $ 1 $ and $ k $ ) that specify the color of each piece in the order of increasing price. If there are multiple ways to color the pieces using $ k $ colors, you can output any of them.

输入输出样例

输入样例 #1

3

输出样例 #1

2
1 1 2 

输入样例 #2

4

输出样例 #2

2
2 1 1 2

说明

In the first input, the colors for first, second and third pieces of jewelry having respective prices $ 2 $ , $ 3 $ and $ 4 $ are $ 1 $ , $ 1 $ and $ 2 $ respectively. In this case, as $ 2 $ is a prime divisor of $ 4 $ , colors of jewelry having prices $ 2 $ and $ 4 $ must be distinct.