思路

全组两两互质约束与最少组数剪枝，避免只检查组代表。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int n,best;vector<int>a,groups[10];int gcd2(int a,int b){return b?gcd2(b,a%b):a;}void dfs(int i,int used){if(used>=best)return;if(i==n){best=used;return;}for(int j=0;j<used;j++){bool ok=true;for(int x:groups[j])if(gcd2(x,a[i])!=1)ok=false;if(ok){groups[j].push_back(a[i]);dfs(i+1,used);groups[j].pop_back();}}groups[used].push_back(a[i]);dfs(i+1,used+1);groups[used].pop_back();}int main(){cin>>n;a.resize(n);for(int &x:a)cin>>x;best=n;dfs(0,0);cout<<best<<'\n';}