776B - Sherlock and his girlfriend - CodeForces Solution

#include<bits/stdc++.h>
#include<cstring>
#define ll long long
#define lowbit(x) (x&(-x))
#define rep(a,b) for(int i=a;i<=b;i++)
#define rrep(a,b) for(int j=a;j<=b;j++)
#define pre(a,b) for(int i=a;i>=b;i--)
#define ppre(a,b) for(int j=a;j>=b;j--)
#define ac puts("Yes")
#define wa puts("No")
#define pb push_back
#define PII pair<int,int>
using namespace std;
const int mod1=998244353;
const int mod2=1e9+7;
const int N=2e5+10;
bool st[N]={1,1};
ll a[N],k;
void ol(){
	for(int i=2;i<=100010;i++){
		if(!st[i])a[++k]=i;
		for(int j=1;j<=k;j++){
			if(i*a[j]>100010)break;
			st[i*a[j]]=1;
			if(i%a[j]==0)break;
		}
	}
}
ll b[N],id[N];
int main(){
	ol();
	int n,k;
	cin>>n;
	if(n<3)k=1;
	else k=2;
	cout<<k<<endl;
	cout<<1<<" ";
	rep(3,n+1)
	if(!st[i])cout<<1<<" ";
	else cout<<2<<" "; 
	return 0;
}