D – Composite Coloring VJ

#include<bits/stdc++.h>
#define ll long long
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const ll nl=1e18;
/*
给1000之内的数上色，拥有大于1的公因数的两个数就可以涂同一种颜色，输出任意一种涂色方案以及所用颜色数量
可以发现不需要求gcd，只要找出每个数除1以外的最小因数，发现1000以内所有数的因数是固定的，找出这些数，发现有11个
2 3 5 7 11 13 17 19 23 29 31
1 2 3 4  5  6  7  8  9 10 11
将他们存入数组，对输入的每个数，依次判断能否整除这11个数，然后用map标记c中第一个能整除的数
*/
int main()
{
    speed_up;
    int t;
    map<int,int>m;
    cin>>t;
    while(t--)
    {
        int n;
        m.clear();
        cin>>n;
        int p=1,a[n],b[n]= {0},c[11]= {2,3,5,7,11,13,17,19,23,29,31};
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<11; j++)
            {
                if(a[i]%c[j]==0)
                {
                    if(m[c[j]]==0)
                    {
                        m[c[j]]=p;
                        p++;//用的颜色数
                    }
                    b[i]=m[c[j]];
                    break;
                }
            }
        }
        cout<<p-1<<endl;
        for(int i=0; i<n; i++)
        {
            cout<<b[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}