1623：Sherlock and His Girlfriend

题目描述

Sherlock 有了一个新女友（这太不像他了！）。情人节到了，他想送给女友一些珠宝当做礼物。

他买了 $n$ 件珠宝。第 $i$ 件的价值是 $i+1$。那就是说，珠宝的价值分别为 $2,3,4,\cdots,n+1$。

Watson 挑战 Sherlock，让他给这些珠宝染色，使得一件珠宝的价格是另一件的质因子时，两件珠宝的颜色不同。并且，Watson 要求他最小化颜色的使用数。

请帮助 Sherlock 完成这个简单的任务。

输入格式

只有一行一个整数 $n$，表示珠宝件数。

输出格式

第一行一个整数 $k$，表示最少的染色数；

第二行 $n$ 个整数，表示第 $1$ 到第 $n$ 件珠宝被染成的颜色。若有多种答案，输出任意一种。

样例

样例输入 #1

3

样例输出 #1

2
1 1 2

样例解释 #1

• $n=3$，珠宝价值分别为 $2,3,4$。
• 条件：如果一件珠宝的价值是另一件的质因子，则颜色必须不同。
• 质因子关系：
  • $2$ 是 $4$ 的质因子，所以珠宝 $2$（价值 $2$）和珠宝 $4$（价值 $4$）必须不同色。
• 最少需要 $2$ 种颜色。
• 一种染色方案：珠宝 $2$ 染颜色 $1$，珠宝 $3$ 染颜色 $1$，珠宝 $4$ 染颜色 $2$。
• 输出：第一行 $2$，第二行 1 1 2（分别对应价值 $2,3,4$ 的珠宝）。

样例输入 #2

4

样例输出 #2

2
2 1 1 2

样例解释 #2

• $n=4$，珠宝价值 $2,3,4,5$。
• 质因子关系：
  • $2$ 是 $4$ 的质因子，所以珠宝 $2$ 和 $4$ 必须不同色。
  • 其他没有质因子关系（$5$ 是质数，没有其他珠宝以它为因子）。
• 最少需要 $2$ 种颜色。
• 一种方案：珠宝 $2$ 染颜色 $2$，珠宝 $3$ 染颜色 $1$，珠宝 $4$ 染颜色 $1$，珠宝 $5$ 染颜色 $2$。
• 输出：第一行 $2$，第二行 2 1 1 2。

数据范围

对于全部数据，$1 \le n \le 10^5$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题等价于：给 $2$ 到 $n+1$ 这些数染色，如果 $a$ 是 $b$ 的质因子，则 $a$ 和 $b$ 颜色不同。求最小颜色数并输出一种方案。

观察：如果我们将所有质数染成同一种颜色，合数染成另一种颜色，那么质因子关系只存在于质数和它的倍数之间，且质数与它的倍数颜色不同。这需要两种颜色。但是否存在一种颜色就够了？如果只用一种颜色，那么质数和它的倍数必须同色，但条件要求不同色，矛盾。所以至少需要两种颜色。

那么两种颜色是否足够？我们可以将所有质数染颜色 $1$，所有合数染颜色 $2$。这样，如果 $a$ 是 $b$ 的质因子，则 $a$ 是质数（因为质因子是质数），$b$ 是合数（因为 $b$ 有质因子 $a$ 且 $b \neq a$，除非 $b$ 也是质数且 $a=b$，但 $a$ 是 $b$ 的质因子且 $a \neq b$ 时 $b$ 一定是合数）。因此 $a$ 颜色 $1$，$b$ 颜色 $2$，满足条件。如果 $b$ 也是质数，那么 $a$ 和 $b$ 都是质数，颜色相同，但此时 $a$ 是 $b$ 的质因子意味着 $a=b$（因为质数只有本身和 $1$ 是因子，而 $1$ 不在范围内），但 $a \neq b$ 时不可能。所以不会出现质数是另一个质数的质因子的情况（除了本身）。因此两种颜色总是足够的。

所以答案：

• 如果 $n+1 \le 3$（即 $n \le 2$），所有数都是质数（$2$ 和 $3$），那么只需要一种颜色（因为没有质因子关系）。但 $n=2$ 时珠宝价值 $2,3$，它们互不为质因子，可以同色。所以 $k=1$。
• 否则 $k=2$。

染色方案：对于 $i$ 从 $2$ 到 $n+1$，如果 $i$ 是质数则染颜色 $1$，否则染颜色 $2$。

注意：$n$ 可能为 $1$，此时只有一件珠宝价值 $2$，可以染任何颜色，最少颜色数为 $1$。