题目描述
代码
package shulun;
import java.util.Scanner;
public class 夏洛克和他的女朋友 {
/**
* @param args
*/
public static int N=(int) (1e5+10);
public static int primes[]=new int [N];
public static boolean st[]=new boolean[N];
public static int cnt=0;
public static void init(int n) {
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
int n =scanner.nextInt();
if(n<=2){
System.out.println(1);
for(int i=1;i<=n;i++){
System.out.print(1+" ");
}
}else{
init(N-1);
System.out.println(2);
for(int i=2;i<=n+1;i++){
if(st[i]) System.out.print(1+" ");
else{
System.out.print(2+" ");
}
}
}
}
}