依次枚举每一个数，放入之前的组或新开一个组
注意u==n之后要return 不然会继续搜索，造成数组越界

#include<iostream>
#include<vector>
using namespace std;
const int N = 15;
int n;
int a[N];
vector<int> f[N];
int ans = N;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
bool check(int u,int num)//第u组能不能容纳num
{
    for(int i=0;i<f[u].size();++i){
        if(gcd(f[u][i],num)>1)
            return false;
    }
    return true;
}
void dfs(int u,int c)//第几个数,用了几个组了
{
    if(u==n){
        ans =min(c,ans);
        return;
        //cout<<"As"<<endl;
    }
    //加入前面存在的组
    for(int i=0;i<c;++i){
        if(check(i,a[u])){
            f[i].push_back(a[u]);
            dfs(u+1,c);
            f[i].pop_back();
        }
    }
    //另开一个组
    f[c].push_back(a[u]);
    dfs(u+1,c+1);
    f[c].pop_back();
}
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    dfs(0,0);
    cout<<ans<<endl;
    return 0;
}