递归组合型搜索+gcd
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n;
int p[N];
int group[N][N];
int ans = N;
bool st[N];//判断当前每个数被用过。
int gcd(int a, int b){
return b ? gcd(b,a % b):a;
}
bool chk(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){
if(g >= ans) return ;//如果当前组元素的数量大于等于ans了，就不是最优解了
if(tc == n){//如果搜完了n个元素，说明把每个元素分给各个组了
ans = g;
}
bool flag = true;
for(int i = start; i < n; i++ ){
if(!st[i] && chk(group[g],gc,i)){//如果该数没有被访问过，且i这个元素和group[g]组的元素是互质的。
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);
/*1：为先搜第一组
第一个0：指该组中有0个元素
第二个0：当前一共搜了0个元素
第三个0：这组从0号下标开始搜
*/
//组合型搜索
cout << ans << endl;
return 0;
}
