题目链接：

---

题意：给你一个n，要你填充 下标由2 ~ n 的数组a_i，要求下标互质的俩个数不能相等，并且数组中最大值最小化。

思路：打个素数表，每个质数肯定互质所以我们令第一个质数为1，第二个质数为2...依次类推，然后根据 ，合数就让它等于第一个分解的质数啦。 

AC代码：

1 #include
     
       2 using namespace std; 3 const int MAXN= 2e5 +5; 4 int vis[MAXN]; 5 int a[MAXN]; 6 int n; 7 void init() 8 { 9     vis[0] = 1;10     vis[1] = 1;11     for(int i = 2;i < MAXN;i ++)12     {13         if(! vis[i])14         {15             vis[i] = 0;16             for(int j = 2*i;j <= MAXN; j += i)17             {18                 vis[j] = 1;19             }20         }21     }22 }23 int gcd(int a,int b)24 {25     if(b == 0)26     return a;27     else return gcd(b,a%b);28 }29 int main()30 {31     int n;32     scanf("%d",&n);33     memset(vis,0,sizeof(vis));34     init();35     int cnt = 1;36     for(int i = 2;i <= n;i++)37     {38         if(!vis[i]) a[i] = cnt++;39         else40         {41             for(int j = 2;j <= i;j++)42             {43                 if(gcd(i,j) != 1)44                 {45                     a[i] = a[j];46                     break;47                 }48             }49         }50     }51     for(int i = 2;i <= n;i++)52     {53         printf("%d ",a[i]);54     }55     return 0;56 }