众所周知，这道题翻译有点小问题。

\(Description:\)

题目要求给序列 2~n+1 涂色，同时要求每个数和他的质因数的颜色不同

\(Sample\) \(Input:\)

3

\(Sample\) \(Output\):

2

1 1 2

我一看，好一题分解质因数，看我\(o(n\sqrt n)\) 随便*。

好吧，好像写不出来，那么考虑别的做法。

首先观察质因数的定义：

百度百科：

每个合数都可以写成几个质数相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。

简单来讲各位都知道质因数一定是质数。那么质数直接又互质，所以可以分为同一种颜色。

那么再考虑不可能有一个合数为另一个合数的质因数。

显然成立。那么其实只有质数和合数两种颜色。

筛法筛一遍，然后质数合数判一判。

一般都有质数合数。

但一个序列没有,对于本题是：

2，3

因为这个序列没有合数。

那么特判一下。

#include
    
     using namespace std;int n,cnt;const int MAXN=1e5;int vis[MAXN+5],p[MAXN+5];int main(){    scanf("%d",&n);    for(int i=2;i<=n+1;++i){        if(!vis[i])p[++cnt]=i;        for(int j=1;j<=cnt && i*p[j]<=n+1;++j){            vis[i*p[j]]=1;            if(i%p[j]==0)break;        }    }    if(n<3)putchar('1');    else putchar('2');    putchar('\n');    for(int i=2;i<=n+1;++i)        if(!vis[i])printf("1 ");        else printf("2 ");    putchar('\n');    return 0;}