<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

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

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

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

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

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

输入格式

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

输出格式

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

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

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

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

数据范围

$1 \\le n \\le 10^5$

输入样例1：

3

输出样例1：

2
1 1 2

输入样例2：

4

输出样例2：

2
2 1 1 2

思路

这题显然是个构造题，观察样例容易猜出颜色个数最优为$\textbf 2$(当$\textbf{3≤n}$)

证明如下：

具体来说，对于每个$3≤n$，我们枚举第$i$枚珠宝

• 如果$i+1$为质数，给这个珠宝涂上颜色$1$
• 如果$i+1$不是质数，给这个珠宝涂上颜色$2$

如果这种方案不符合题意，那么一定有两个数$a,b$ 不满足题意，而两个数一个是质数，一个是合数，所以颜色一定不同，矛盾！

显然，对于每个大于$3≤n$，只用一种颜色会使第一件宝物和第三件的宝物颜色相同，不符合题意。

综上，当$3≤n$时，最优情况就是用两种颜色

当$n\le 2$时需要 特判，具体细节见代码

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int primes[N],cnt;
bool is_prime[N];
void get_primes (int n) {
    memset (is_prime,true,sizeof (is_prime));
    is_prime[1] = false;
    for (int i = 2;i <= n;i++) {
        if (is_prime[i]) primes[++cnt] = i;
        for (int j = 1;primes[j] * i <= n;j++) {
            is_prime[primes[j] * i] = false;
            if (i % primes[j] == 0) break;
        }
    }
}
int main () {
    cin >> n;
    get_primes (n + 1);
    if (n <= 2) puts ("1");
    else puts ("2");
    for (int i = 2;i <= n + 1;i++) {
        if (is_prime[i]) cout << 1 << ' ';
        else cout << 2 << ' ';
    }
    cout << endl;
    return 0;
}