Sherlock and his girlfriend

time limit per test 1 second memory limit per test 256 megabytes
Sherlock has a new girlfriend (so unlike him!). Valentine’s day is coming and he wants to gift her some jewelry.

He bought n pieces of jewelry. The i-th piece has price equal to i+1, that is, the prices of the jewelry are 2,3,4,… n+1.

Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don’t have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.

Help Sherlock complete this trivial task.

传送门:CF776B

Input

The only line contains single integer n (1≤n≤100000) — the number of jewelry pieces.

Output

The first line of output should contain a single integer k, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.
The next line should consist of n space-separated integers (between 1 and k) that specify the color of each piece in the order of increasing price.
If there are multiple ways to color the pieces using k colors, you can output any of them.

Sample Input

1
3

Sample Output

1
2
2
1 1 2

题解

一开始看错题了尴尬…注意是素因数
那么所有素数可以涂成同一种颜色,而其他的涂另外一种颜色就好了
注意1和2的特判颜色种数

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;  
public class Main {
static boolean []prime;
public static void main(String[] args) {
FastScanner sc= new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
prime =new boolean [100050];
makePrime(100005);
while(sc.hasNext()){
int n=sc.nextInt();
int[]shu=new int[n+1];
for(int i=1;i<=n;i++) shu[i]=i+1;
int[]flag=new int[n+1];
for(int i=1;i<=n;i++){
if(prime[shu[i]]==true) flag[i]=1;
else flag[i]=2;
}
if(n==1||n==2) pw.println(1);
else pw.println(2);
for(int i=1;i<=n;i++){
pw.print(flag[i]+" ");
}
pw.flush();
}
}
public static void makePrime(int n){ //素数筛法
Arrays.fill(prime, true);
prime[0]=false;
prime[1]=false;
for(int i=2;i<=n+1;i++)
for(int j=i+i;j<=n+1;j+=i){
prime[j]=false;
}
}
}