题目描述

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

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

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

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

输入格式

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

输出格式

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

样例

样例输入 1

样例输出 1

2
1 1 2

样例输入 2

样例输出 2

2
2 1 1 2

思路：

这道题十分简单，只需要把质数变为同一种颜色，合数变为同一种颜色就行了。代码如下：

#include<bits/stdc++.h>

using namespace std;

bool a[10000005]={};

int  f[10000005],sum[10000005];

void SZS(int n){

	memset(a,1,sizeof a);

	int toto=0;

	for(int i=2;i<=n;i++){

		if(a[i])

			f[++toto]=i;

		for(int j=1;j<=toto&&i*f[j]<=n;j++){

			a[i*f[j]]=0;

			if(i%f[j]==0)

				break;

		}                         //线性筛

	}

}

int main(){

	int n;

	scanf("%d",&n);

	SZS(n+1);       //因为n的j价值是n+1，所以需要在处理时加1；

	if(n<=2){

		printf("1\n");  //如果n=1,那么只有2，只用涂一种颜色

						//如果n=2,那么价值为2，3，均是质数，也只用涂一种颜色；

	}

	else

	    printf("2\n");  //如果n>2，那么至少就有2,3,4，一定要涂两种颜色；

	for(int i=2;i<=n+1;i++){

		if(a[i]){

			printf("1 ");	//如果是质数，就涂1；

		}

		else

			printf("2 ");	//合数涂2；

		//因为第一个的价值是2，所以不用考虑1这种既不是质数又不是合数的情况；

	}

}

巴特西

Sherlock and His Girlfriend题解