<=点个赞吧QWQ

$\Huge\color{gold}{题目传送门}$

算法

(筛质数) $O(n)$

这里我们用欧拉法来做，时间复杂度是线性的，筛完后进行第二步：找答案。

答案分两种情况：
1.n <= 2: 很显然只要1种颜色就可以了
2.n >= 3: 我们把数字分成两类–>合数和质数，显然可得合数染成1，质数染成2

时间复杂度

欧拉法是线性的，而第二步也是线性的，所以总的就是$O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int primes[N], cnt;
bool is_prime[N];

void get(int n)
{
    is_prime[0] = is_prime[1] = true;

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

int main()
{
    int n = 0;
    scanf("%d", &n);
    get(n + 1);

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

    for (int i = 2; i <= n + 1; ++ i )
    {
        if (!is_prime[i]) printf("1 ");
        else printf("2 ");
    }
    return 0;
}