rt

for(int i=2;i*i<=n;i++) sqr.push_back(i*i);
for(int i=1;i<=n;i++) a[i]=i;
for(int i=sqr.size()-1;i>=0;i--){
	for(int j=sqr[i];j<=n;j+=sqr[i])
      		if(a[j]%sqr[i]==0) 
          		a[j]/=sqr[i];
}