题面

题目传送门

Sherlock 有了一个新女友（这太不像他了！）。情人节到了，他想送给女友一些珠宝当做礼物。

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

Watson 挑战 Sherlock，让他给这些珠宝染色，使得一件珠宝的价格是另一件的质因子时，两件珠宝的颜色不同。并且，Watson 要求他最小化颜色的使用数。

请帮助 Sherlock 完成这个简单的任务。

输入格式

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

输出格式

第一行一个整数 $k$，表示最少的染色数；
第二行 $n$ 个整数，表示第 $1$ 到第 $n$ 件珠宝被染成的颜色。若有多种答案，输出任意一种。

思路

对于这一段区间内的所有合数，他们一定不互为质因子（都不是质数了当然不互为质因子），所以只需要把区间内的质数全部染上一种颜色，合数染上另一种颜色，只需 2 种颜色。

注意：当 $n<=2$ 时，只需要一种颜色，所以要特判。

代码

#include<bits/stdc++.h>
using namespace std;
int pr[1000005]={2};
long long top=0;
int is[1000005];
int n;
void prime_oulashai(){
    top=1;
    for (int i=2;i<=1000000;i++){
        if (!is[i]){
            pr[top++]=i;
        }
        for (int j=0;j<=top-1;j++){
            if (i*pr[j]>1000000){
                break;
            }
            is[i*pr[j]]=1;
            if (i%pr[j]==0){
                break;
            }
        }
    }
}
int main(){
	cin>>n;
	if (n==1){
		cout<<"1\n1";
		return 0;
	}
	if (n==2){
		cout<<"1\n1 1";
		return 0;
	}
	prime_oulashai();
	is[2]=0;
	cout<<2<<endl;
	for (int i=1;i<=n;i++){
		if (is[i+1]){
			cout<<1<<" ";
		}else{
			cout<<2<<" ";
		}
	}
}