思路分析：

一：这种分组的题有固定的套路，一般就是枚举元素分配到哪个组和分配到新的组，取个最优解

二：类似题目地址：

https://www.acwing.com/problem/content/167/

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 15;

int arr[N];
vector<int> g[N];
int n;
int ans;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(auto& group, int u)
{
    for (int j = 0; j < group.size(); j ++ )
        if (gcd(group[j], u) > 1)
            return false;
    return true;
}

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

int main(){
    cin >> n;
    for(int i = 0;i < n;++i) cin >> arr[i];
    ans = 0x3f3f3f3f;
    dfs(0, 0);
    cout << ans << endl;
}