埃氏筛：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n;
bool flag[maxn];

int main() {
	scanf("%d", &n);
	flag[0] = flag[1] = 1;
	for (int i = 2; i * i <= n + 1; i++) {
		if (!flag[i]) {
			for (int j = i << 1; j <= n + 1; j += i) {
				flag[j] = 1;
			}
		}
	} // 埃氏筛的优化：一个数的最大因子不会超过sqrt(n)
	puts(n < 3 ? "1" : "2");
	for (int i = 2; i <= n + 1; i++) {
		printf("%d ", flag[i] + 1);
	}
	return 0;
}