这道题其实不难。
\(\gcd(i,j)=1\)，其实就是 \(i\) 与 \(j\) 互质。
如果 \(i\) 与 \(j\) 不互质，那么我们一定要让 \(a_i\) 与 \(a_j\) 相同，只有这样，才能使 \(a\) 序列中的最大值最小化。
所以，我们可以使用埃氏筛法，当筛到质数时，给它和它的倍数都赋值为一个新数。
AC Code:
#include<iostream>
using namespace std;
int n;
int a[100005];
int c;
signed main(){
cin>>n;
for(int i=2;i<=n;i++){
if(a[i])continue; //非质数
c++; //一个新数字
for(int j=1;j*i<=n;j++){
a[i*j]=c; //倍数赋值为 c
}
}
for(int i=2;i<=n;i++){ //从 2 开始
cout<<a[i]<<" ";
}
return 0; //完美收尾
}