题目描述
原题来自：Codeforces Round #400 B.
Sherlock 有了一个新女友（这太不像他了！）。情人节到了，他想送给女友一些珠宝当做礼物。
他买了
n
n 件珠宝。第
i
i 件的价值是
i+1
i+1。那就是说，珠宝的价值分别为
2,3,4,\cdots ,n+1
2,3,4,⋯,n+1。
Watson 挑战 Sherlock，让他给这些珠宝染色，使得一件珠宝的价格是另一件的质因子时，两件珠宝的颜色不同。并且，Watson 要求他最小化颜色的使用数。
请帮助 Sherlock 完成这个简单的任务。
输入
只有一行一个整数
n
n，表示珠宝件数。
输出
第一行一个整数
k
k，表示最少的染色数；
第二行
n
n 个整数，表示第
1
1 到第
n
n 件珠宝被染成的颜色。若有多种答案，输出任意一种。
样例输入
【样例输入1】
3
【样例输入2】
4
样例输出
【样例输出1】
2
1 1 2
【样例输出2】
2
2 1 1 2
提示
样例说明
因为
2
2 是
4
4 的一个质因子，因此第一件珠宝与第三件珠宝的颜色必须不同。
数据范围与提示
对于全部数据，
1\le n\le 10^5
1≤n≤105。
来源/分类
ybttg 数论 埃及筛及欧拉筛