夏洛克和他的女朋友—线性筛—逻辑

输入样例1：

3

输出样例1：

2
1 1 2

输入样例2：

4

输出样例2：

2
2 1 1 2

1、一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同，则等价于每一个合数与它的每一个质因子的颜色均不同，等价于质数和合数染的颜色一定不同，因此质数和合数形成了一个二分图，最多只会染两种颜色，当第n件宝贝的价值是n + 1 >= 4时，则表示有两种颜色，否则只有一种颜色
2、通过线性筛法把所有的质数筛出来，将所有的质数染成1的颜色，合数染色2的颜色 

#include 
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
bool iscomp[100000005];  //是不是合数
int arr[N];
int num;
void isCop(bool iscomp[], int n)
{
	iscomp[1] = 1;  //1的特判
	for (int i = 2;i <= n / i;i++)
	{
		if (iscomp[i] == 0)  //如果是素数
			for (int j = i * i;j <= n;j += i) //将他的倍数记为合数
				iscomp[j] = 1;   //标记
	}
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//数据预处理
	int n = 1e5+10;//n代表的是判断的数据范围；
	isCop(iscomp, n);
	int num;
	cin >> num;
	if (num > 2) {
		cout << '2' << endl;
	}
	else cout << '1' << endl;
	for (int i = 1;i <= num;i++) {
		if (iscomp[i+1])cout << '2' << ' ';
		else cout << '1' << ' ';
	}
	return 0;
}