Codeforces Round #563 (Div. 2) C - Ehab and a Special Coloring Problem
You're given an integer n. For every integer i from 2 to n, assign a positive integer ai
such that the following conditions hold:
- For any pair of integers (i,j)
, if i and j are coprime, ai≠aj
- .
- The maximal value of all ai
- should be minimized (that is, as small as possible).
A pair of integers is called coprime if their greatest common divisor is 1
.
Input
The only line contains the integer n
(2≤n≤105
).
Output
Print n−1
integers, a2, a3, …, an (1≤ai≤n
).
If there are multiple solutions, print any of them.
Examples
Input
Copy
4
Output
Copy
1 2 1
Input
Copy
3
Output
Copy
2 1
Note
In the first example, notice that 3
and 4 are coprime, so a3≠a4. Also, notice that a=[1,2,3] satisfies the first condition, but it's not a correct answer because its maximal value is 3
.
思路：模拟一下埃筛就好了
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Max 105
#include<queue>
int a[105000];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int sum=0;
for(int i=2;i<=n;i++)
{
if(a[i]==0)
{
sum++;
for(int j=1;j*i<=n;j++)
{
if(a[i*j]==0) a[i*j]=sum;
}
}
}
printf("%d",a[2]);
for(int i=3;i<=n;i++) printf(" %d",a[i]);
printf("\n");
}
}
