按顺序考虑每一个数，考虑把它放到哪个组里面

/*
    参考墨染空dalao的代码

    按顺序考虑每一个数，考虑把它放到哪个组里面
*/  

#include <iostream>
#include <vector>

using namespace std;

const int N = 10;

int n;
int a[N]; // 存数字
int ans=N, len; // ans:全局答案 len:当前开的组数 
vector<int> g[N]; // 每一组

int gcd(int x,int y)
{
    return y ? gcd(y, x % y) : x;
}

bool check(int u,int c) // u:当前组，c:组编号，判断当前数能否放到这一组中
{
    for(int i=0;i<g[c].size();i++)
        if(gcd(g[c][i], u) > 1) return false;

    return true;
}

void dfs(int u)
{
    if(u==n){ // 处理完所有数字了
        ans = min(ans,len);
        return ;
    }

    // 不开新组
    for(int i = 0;i < len;i++){
        if(check(a[u], i)){
            g[i].push_back(a[u]);
            dfs(u+1);
            g[i].pop_back(); // 恢复现场
        }
    }

    // 开新组
    g[len ++ ].push_back(a[u]);
    dfs(u + 1);
    g[-- len].pop_back();

}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    dfs(0); // 从下标为0的数字开始搜

    cout<<ans<<endl;

    return 0;
}

不是很懂的一段代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

int n;
int p[N];
int group[N][N];
bool st[N];
int ans=N;

int gcd(int a,int b)  // 判断两个数是否互质
{
    return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i)
{
    for(int j=0;j<gc;j++)
        if (gcd(p[group[j]], p[i]) > 1)
            return false;
    return true;
}

void dfs(int g,int gc,int tc,int start) 
{                   //// dfs(当前组，组内元素，当前一共搜了多少个元素，这一组从start开始搜)
    if (g >= ans) return;
    if(tc == n) ans=g;

    bool flag=true;
    for(int i=start;i<n;i++)
        if(!st[i] && check(group[g],gc,i))
        {
            st[i]=true;
            group[g][gc]=i;
            dfs(g, gc+1, tc+1, i+1);
            st[i]=false;

            flag=false;
        }

    if(flag) dfs(g+1, 0, tc, 0);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>p[i];

    dfs(1,0,0,0);

    cout<<ans<<endl;

    return 0;

}