分析

• 可以将这个题抽象成一个图，所有珠宝的价值是图中的顶点，当一个珠宝的价格是另一个珠宝的质因子时，我们可以在这两个点之间连接一条边。

• 如果这样建图的话，我们可以将质数放在左边，合数放在右边，则左边内部和右边内部是不可能有边的，边只在左右两边之间，因此此图是一个二分图，一个图是二分图，等价于该图可以二染色。

• 因此对于本题而言，当珠宝的数量小于等于2个时，只需要一种颜色即可，否则需要两种颜色；代码中我们不需要将图建立出来，我们只需要把1~100000中的质数全部筛出来，然后将所有的质数染成一种颜色，所有的合数染成另一种颜色即可。

代码

#include <iostream>

using namespace std;

const int N = 100010;

int n;
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() {

    cin >> n;

    init(n + 1);

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

    for (int i = 2; i <= n + 1; i++)
        if (!st[i]) printf("1 ");
        else printf("2 ");

    return 0;
}