难度： 黄

算法： 素数，质数判断，筛法

发现，当 $n<3$ 时，可以全部都取一种颜色。

如果 $n\ge 3$，显然一种颜色不行，所以至少要两种颜色。我们可以根据人类智慧得到，将所有质数记为颜色 $1$，合数记为颜色 $2$。这样一来所有合数都与质数不同色，那么所有合数都与它们的质因子同色。而质数没有除自身以外的质因子。

#include<bits/stdc++.h>
using namespace std;
int f[100010],pr[100010],pc,n;
int main(){
	scanf("%d",&n);
	n++;
	for(int i=2;i<=n;i++){
		if(!f[i]) pr[++pc]=i;
		for(int j=1;j<=pc;j++){
			if(i*pr[j]>n) break;
			if(!f[i*pr[j]]) f[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
	if(n<=3) printf("1\n");
	else printf("2\n");
	for(int i=2;i<=n;i++){
		if(f[i]==0) printf("1");
		else printf("2");
		if(i!=n) printf(" ");
	}
}