详细请看注释

可以添加两个剪枝将代码优化到15ms

参考代码

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

using namespace std;

const int N = 10;

int n, vis[N], a[N], group[N][N];
int res = N;

/*
    本题搜索方式为：依次枚举每一组中选哪些数，通俗理解：拿着篮子，依次扫描每个苹果，往篮子里放可以放的！

    两个剪枝优化：
            1. if(g >= res) return; ---> 若当前分支搜到的答案比其他分支搜到的大，直接丢掉！
            2. if(len == 0) break; ----> 当前组长度为0，则开新组，可以开新组这说明当前数也只能放到新组，
                                         等效于放到之后的任意新组，可以直接剪枝

        两次剪枝后用时：15ms

    其他优化：每次dfs遍历的起始位置可以使用上一次的位置的下一个位置，可以极大减少冗余遍历，即按照组合数遍历！

    注意点：按照这种搜索方式，（除了组内第一个元素）其他元素放入组中后，仍然需要回溯！
        原因：可以放入本组，也可以放入之后可以放入的组，不一定放入到本组是最优的，需要全部爆搜一遍！
*/

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

// 当前组 当前组容量 准备加入当前组的数的下标
bool check(int group[], int len, int u){
    for(int i = 0; i < len; i ++)
        if(gcd(a[u], a[group[i]]) > 1) return false;
    return true;
}

// 当前组编号 当前组容量 已遍历的数个数 上一次遍历数字的下一个位置
void dfs(int g, int len, int u, int start){
    // 剪枝优化一：若当前分支搜到的答案比其他分支搜到的大，直接丢掉！
    if(g >= res) return;
    if(u == n){
        res = g;
        return;
    }

    bool flag = true;
    for(int i = start; i < n; i ++){
        if(!vis[i] && check(group[g], len, i)){
            group[g][len] = i, vis[i] = true;
            dfs(g, len + 1, u + 1, i);

            // 此处恢复现场表示：放到当前组不一定最优，可以将其拿出来试所有情况！
            vis[i] = false, flag = false;

            // 剪枝优化二：当前组长度为0，则开新组，可以开新组这说明当前数也只能放到新组，等效于放到之后的任意新组，可以直接剪枝
            if(len == 0) break;
        }
    }
    // 若放不到当前所有组，只能新开一个组
    if(flag) dfs(g + 1, 0, u, 0);
}

int main(){
     cin >> n;
     for(int i = 0; i < n; i ++) cin >> a[i];
     dfs(1, 0, 0, 0);
     cout << res << endl;
     return 0;
}