原题链接
夏洛克有了一个新女友（这太不像他了！）。
情人节到了，他想送给女友一些珠宝当做礼物。
他买了 n 件珠宝，第 i 件的价值是 i+1，也就是说，珠宝的价值分别为 2,3,…,n+1。
华生挑战夏洛克，让他给这些珠宝染色，使得一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同。
并且，华生要求他使用的颜色数尽可能少。
请帮助夏洛克完成这个简单的任务。
输入格式
只有一行一个整数 n，表示珠宝件数。
输出格式
第一行一个整数 k，表示所使用的颜色数；
第二行 n 个整数，表示第 1 到第 n 件珠宝被染成的颜色。
若有多种答案，输出任意一种。
请用 1 到 k 表示你用到的颜色。
数据范围
1≤n≤105
输入样例1：
3
输出样例1：
2
1 1 2
输入样例2：
4
输出样例2：
2
2 1 1 2
分析：从2-n+1中，如果一个数是另一个数的质因子，这两个数就不同颜色。以下为图论内容：我们把每个数都看成一个点，如果两个数是不同颜色即一个数是另一个数的质因子，那么就把这两个点连起来。这也就引出了这个题的特殊性：所有的边都是一边是质数，一边是合数。这个图就是个二分图，完全可以用高级的二分图染色来解决。那么我们换一个角度想想，依照题意的话，我们完全可以质数都涂一种颜色，合数都涂另一种颜色，这也就完美的符合了题意。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N = 100010; int primes[N], cnt; bool st[N]; void init(int n) { for (int i=2; i<= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] * i <= n; j ++ ) { st[i * primes[j]] = true; if (i % primes[j] == 0) break; } } } int main() { int n; cin >> n; init(n + 1); if (n <= 2) puts("1"); else puts("2"); for (int i = 2; i <= n + 1; i ++ ) if (!st[i]) printf("1 "); else printf("2 "); return 0; }
