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

$即从一个质数向合数连一条边，最后会构成二分图$
$注：质数之间彼此互质没有连边，合数之间不满足题意也没有连边$
$当n<=2时只有质数，输出1，由二分图可知其他情况均为2$

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

const int N=1e5+10;
int primes[N],cnt;
bool st[N];

void init(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    int n;
    cin>>n;

    init(n+1);

    if(n<=2) puts("1");
    else puts("2");

    for(int i=2;i<=n+1;i++){    //他买了 n 件珠宝，第 i 件的价值是 i+1
        if(!st[i]) printf("1 ");    //!st为true代表素数
        else printf("2 ");
    }
    return 0;
}