《CF776B Sherlock and his girlfriend》
题目描述
Sherlock 有一个新女朋友。现在情人节就要到了，他想送给她一些珠宝。
他买了几件首饰。第 i 件的价格等于 i+1，也就是说，珠宝的价格分别为 2,3,4,…,n+1 。
现在需要给这些珠宝首饰上色。当一件珠宝的价格是另一件珠宝的价格的素因子时，这两件的颜色就不允许相同。此外，要最少化使用的颜色数量。
输入格式
一行，包含单个整数 n(1≤n≤100000) 指珠宝的数量。
输出格式
第一行的输出包含一个整数 K，指最少颜色的颜色种类数。
第二行由 n 个整数（1 到 k）组成，按价格从小到大来表示每件珠宝的颜色。
如果有多种方法，则可以输出它们中的任何一种。
显示翻译
题意翻译
输入输出样例
输入 #1复制
3
输出 #1复制
2 1 1 2
输入 #2复制
4
输出 #2复制
2 2 1 1 2
说明/提示
在第一个样例中，第一、第二和第三件首饰的价格分别为 2、3、4,它们的颜色分别为 1 、1 和 2。
在这种情况下，由于 2 是 4 的因子，所以具有因数 2 和 4 的珠宝的颜色必须是不同的。
Translated by @皎月半洒花。
代码实现：
#include<bits/stdc++.h> using namespace std; int n, arr[100005]; bool vis[100005]; inline void gen() { for(int i=2; i<=n+1; ++i) { if(!vis[i]) { printf("%d ", 1); for(int j=i*2; j<=n+1; j+=i) vis[j] = 1; } else { printf("%d ", 2); } } return; } int main() { scanf("%d", &n); if(n-1 == 0) { printf("1\n1"); exit(0); } if(n-2 == 0) { printf("1\n1 1"); exit(0); } printf("2\n"); gen(); return 0; }