分成互质组

【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

【输入】
第一行是一个正整数n。1 ≤ n ≤ 10。

第二行是n个不大于10000的正整数。

【输出】
一个正整数，即最少需要的组数。

【输入样例】

6
14 20 33 117 143 175

【输出样例】

3

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 11;
int n, a[N], cnt, ans = N;
vector<int> g[N];

bool check(int x, int i)
{
    for(int j = 0; j < g[i].size(); j++){
        if(__gcd(g[i][j], x) > 1)
            return false;
    }
    return true;
}

void dfs(int u)
{
    if(cnt >= ans) return;
    if(u == n) {
        ans = cnt;
        return;
    }
    for(int i = 0; i < cnt; i++)
    {
        if(check(a[u], i))
        {
            g[i].push_back(a[u]);
            dfs(u + 1);
            g[i].pop_back();
        }
    }
    g[cnt++].push_back(a[u]);
    dfs(u + 1);
    g[--cnt].pop_back();
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    dfs(0);
    cout << ans << endl;
    return 0;
}