分析

• 一组一组的考虑，依次考察所有没有分到某组的数据，如果一个数据能放入当前考察的组，则直接放入，如果当前组不能放入任何一个数据了，那么新开一组，知道所有数据都被分到某组内，类似于贪心的过程。

• 这个过程会得到最优解，如果一个数据能放入当前考察的组T，但是却没有放入，而是新开了一组，如果这样做的话可以得到最优解，那么完全可以将这个数据放到组T中，结果仍是最优解。

#include <iostream>

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;
}

// g: 组的编号，gc: 组内元素个数
// tc: 当前一共搜索元素个数，start: 这一组目前搜索到的下标
void dfs(int g, int gc, int tc, int 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;
}