1333F - Kate and imperfection - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
const int M=2e5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,ans[N+5];
int isprime[N+5];
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	ans[1]=1;
	for(int i=2;i<=n;i++){
		if(isprime[i])continue;
		ans[i]=1;
		for(int j=i+i;j<=n;j+=i){
			isprime[j]=1;
			ans[j]=max(ans[j],j/i);
		}
	}
	sort(ans+1,ans+1+n);
	for(int i=2;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}