题目

原题链接：B. Sherlock and his girlfriend

题意

有n个首饰价格为2~n+1。现要为所有首饰染色，若一个商品是另一个商品的素因子，则两个商品不同色。问最后会有多少种颜色，并输出各个首饰的颜色。
参考了其他作者的思路。素数一种色，非素数一种色。

代码

#include<bits/stdc++.h>
using namespace std;
bool pre(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0) return 0;
    }
    return 1;
}
int main() {
    int n,s[100010];
    cin>>n;
    for(int i=1;i<=n;i++){
        if(pre(i+1)) s[i]=1;
        else s[i]=2;
    }
    printf("%d\n",n>2?2:1);
    for(int i=1;i<=n;i++){
        printf("%d",s[i]);
        printf("%c",i==n?'\n':' ');
    } 
    return 0;
}