CF776B Sherlock and his girlfriend

Sherlock 有一个新女朋友。现在情人节就要到了，他想送给她一些珠宝。 他买了几件首饰。第 $i$ 件的价格等于 $i+ 1$，也就是说，珠宝的价格分别为 $2,3,4,\ldots,n + 1$ 。 现在需要给这些珠宝首饰上色。**当一件珠宝的价格是另一件珠宝的价格的素因子时，这两件的颜色就不允许相同。** 此外，要最少化使用的颜色数量。

一行，包含单个整数 $n(1\le n\leq 100000)$ 指珠宝的数量。

第一行的输出包含一个整数 $K$，指最少颜色的颜色种类数。 第二行由 $n$ 个整数（$1$ 到 $k$）组成，按价格从小到大来表示每件珠宝的颜色。 如果有多种方法，则可以输出它们中的任何一种。

在第一个样例中，第一、第二和第三件首饰的价格分别为 $2$、$3$、$4$,它们的颜色分别为 $1$ 、$1$ 和 $2$。 在这种情况下，由于 $2$ 是 $4$ 的因子，所以具有因数 $2$ 和 $4$ 的珠宝的颜色必须是不同的。 Translated by @皎月半洒花。