题解 A1293 【夏洛克和他的女朋友】
AcWing1293 夏洛克和他的女朋友
题目大意：
有 \(n\) 个数分别为 \(2,3...n+1\) ，要将这 \(n\) 个数染色，使得一个是另一个质因子时两个数的颜色不同。
solution：
我们发现可以把这些数分为两个集合，质数和合数，质数不能作为质数的质因子，所以不用考虑质数的颜色关系，即都可为一个颜色，那么合数为另一种颜色就好了。所以我们只用两个颜色即可。
细节处理：
- 别忘了特判只有一个数的情况。
代码
#include
using namespace std;
const int PR=8e5+5,N=1e6+5;
bool vis[N];int pr[PR],cnt;
inline void xxs(){
for(int i=2;i<=N;i++){
if(!vis[i]) pr[++cnt]=i;
for(int j=1;j<=cnt;j++){
if(i*pr[j]>N) break;
vis[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}
}
int main(){
xxs();
int n; scanf("%d",&n);
puts(n>2?"2":"1");
for(int i=2;i<=n+1;i++)
printf(vis[i]?"2 ":"1 ");
return 0;
}