Source : 信息学奥赛一本通(提高篇)
Description

N个点,标号2..n+1,给这些点染色,要求若ab的素因子,则ab的颜色不同,求一种颜色数最少的方案。

Input
一个整数n
Output

第一行一个整数k,表示最少的染色数。第二行n个整数,表示2..n+1的点被染成的颜色。若有多种答案,输出任意一种

Sample Input
3
Sample Output
2
1 1 2
Hint

1 ≤ n ≤ 100000

【算法分析】

注意到这是二分图,一边是素数,一边是合数,把素数都染成1,合数都染成2即可