我用的是状压Dp。
先预处理出可以在一组的集合。
然后对每种状态枚举它的子集进行转移。
像这样子:

    for(i=1;i<(1<<n);i++) 
        for(j=(i-1)&i;j;j=(j-1)&i) 
            f[i]=min(f[i],f[j]+f[i-j]);

$f[i]$ 表示已经把 $i$ 集合里的数安顿好了需要几个组。
属性:min。
时间复杂度: $O(n^2 \times 2^n+3^n)$,
其中 $O(n^2 \times 2^n)$ 是预处理的复杂度,$O(3^n)$ 是枚举子集的复杂度。
只用 $22ms$ 就跑完了所有数据!

Code

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=16,S=(1<<N);

int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

int n;
int a[N],f[S];

int main()
{
    int i,j,k;
    cin>>n;
    for(i=0;i<n;i++) 
        scanf("%d",&a[i]);
    memset(f,0x3f,sizeof f);
    for(i=(1<<n)-1;i>=0;i--) {
        if(f[i]==1) continue;
        for(j=0;j<n;j++) {
            if(!((i>>j)&1)) continue;
            for(k=j+1;k<n;k++) {
                if(!((i>>k)&1)) continue; 
                if(gcd(a[j],a[k])!=1) break;
            }
            if(k<n) break;
        }
        if(j==n) {
            for(j=i;j;j=(j-1)&i) f[j]=1;
//          printf("%d\n",i);
        }   
    }
    for(i=1;i<(1<<n);i++) 
        for(j=(i-1)&i;j;j=(j-1)&i) 
            f[i]=min(f[i],f[j]+f[i-j]);
    cout<<f[(1<<n)-1]<<endl;
    return 0;
}