题目：
分析：
读了读题，数据范围较小，可以考虑dfs。依次枚举每个数能否加到前面的某一个组中，（当然枚举第一个数的时候，前面没有组）,如果能的话，则加入到某一个组中，但总的组的个数不变。如果不能的话，则新建一个组，此时总的组的个数加1，然后把这个数加入到这个新建的组中。直到枚举的这n个数全部在组中。当然从第一个数开始时，此时没有组，所以从dfs(1, 0)开始。话不多说，具体的细节看code吧。
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 25;
vector<int>g[N];//存放组 每组都是互质的数
int ans = N;
int n;
int a[N];
int gcd(int a, int b) {//求最大公因数
if(!b) return a;
return gcd(b, a % b);
}
bool check(int x, int c) {//判断x能否加入到序号为c的这个组中
for(int i = 0; i < g[c].size(); i++) {//枚举c这个组中的每一个元素
if(gcd(x, g[c][i]) > 1) return false;
}
return true;
}
void dfs(int u, int len) {
if(len >= ans) return;//剪枝
if(u > n) {//n个数看完后,更新答案
ans = len;//len >= ans的已被剪枝 则只剩下len < ans的
return;
}
for(int i = 0; i < len; i++) {//枚举前面每一个组
if(check( a[u], i)) {//这个数能加入到前面出现过的组中
g[i].push_back(a[u]);//把这个数加入i这个组
dfs( u + 1, len);//组的个数不变,看下一个数
g[i].pop_back();//回溯
}
}
//如果加入不进去 则新开一个组
g[len].push_back(a[u]);
dfs( u + 1, len + 1);
g[len].pop_back();
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1, 0);//从第一个数开始看,此时没有组数
cout << ans << endl;
return 0;
}