Codeforces 776B. Sherlock and his girlfriend Solution

 Solution in C++: 

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh  

1. #include<bits/stdc++.h> bool prime[100009]; using namespace std; long long i,j,n; void sieve() { memset(prime,1,sizeof(prime)); prime[0]=0; prime[1]=0; for(i=4; i<=100009; i+=2) prime[i]=0; for( i=3; i<=100009; i+=2) { if(prime[i]==1) { for( j=i*2; j<=100009; j+=i) { prime[j]=0; } } } } int main() { cin>>n; sieve(); long long nprime=0,yprime=0; if(n<3) cout<<"1"<<endl; else cout<<"2"<<endl; for(i=2; i<=n+1; i++) { if(prime[i]==1) cout<<"1 "; else cout<<"2 "; } cout<<endl; }