夏洛克和他的女朋友

夏洛克有了一个新女友（这太不像他了！）。

情人节到了，他想送给女友一些珠宝当做礼物。

他买了 n 件珠宝，第 i 件的价值是 i+1，也就是说，珠宝的价值分别为 2,3,…,n+1。

华生挑战夏洛克，让他给这些珠宝染色，使得一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同。

并且，华生要求他使用的颜色数尽可能少。

请帮助夏洛克完成这个简单的任务。

输入格式

只有一行一个整数 n，表示珠宝件数。

输出格式

第一行一个整数 k，表示所使用的颜色数；

第二行 n 个整数，表示第 1 到第 n 件珠宝被染成的颜色。

若有多种答案，输出任意一种。

请用 1 到 k 表示你用到的颜色。

数据范围

1≤n≤100000

输入样例1：

3

输出样例1：

2
1 1 2

输入样例2：

4

输出样例2：

2
2 1 1 2

思路

在给定的范围中，只需要把质数跟合数染成不同颜色就可以了。当n>2时就有质数和合数，只需要2种颜色，n<=2时，只有2跟3两个质数，所以只需要1种颜色

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>
#include <set>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;
typedef long long ll;

int N;
bool st[maxn];
int prime[maxn / 10],cnt;

void get_prime(int N){
    for(int i = 2; i < N; i++){
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= N / i; j++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int main(){
    cin>>N;
    get_prime(N+1);
    if(N<=2) puts("1");
    else puts("2");
    for(int i = 2;i<=N+1;i++){
        if(st[i]) printf("2 ");
        else printf("1 ");
    }
    return 0;
}