#include <iostream>
using namespace std;

int n, a[15], g[15], ans = 15;

int gcd(int a, int b){ //辗转相除法
    while(b){
        int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

void dfs(int u, int cnt){
    if(cnt > ans) return; //如果当前查找的已经比之前的答案大就不再查找，剪枝
    if(u > n){ //准备枚举第n+1个，意味着第n个已经枚举完成，到达叶子结点，搜索结束
        ans = min(ans, cnt);
        return;
    }

    for(int i = 1; i <= cnt; i++){ //看看现有的桶里能不能放进去
        bool flag = 1; //这个变量用来判断能不能把第u个数字放入第i个分组
        for(int j = 1; j < u; j++){ //从1开始枚举所有的数字
            if(g[j] == i &&gcd(a[u], a[j]) != 1){ //如果当前枚举到的这个数字在当前枚举到的分组里 \
            且当前数字与a数组第u个数字不是互质的
            //必须要先判断枚举到的第j个数字是不是在第i组，不然会混乱
                flag = 0;
                break;
            }
        }
        if(flag){
            g[u] = i;
            dfs(u + 1, cnt); //继续搜索下一个数字，cnt不变因为没有新建分组
        }
    }
    g[u] = cnt + 1;
    dfs(u + 1, cnt + 1); //继续搜索下一个数字，cnt加一因为新建了一组

}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    g[1] = 1; // 把第一号数字放进第一个分组里 g[第几个数字] = 第几个分组
    dfs(2, 1); //从第二个数字开始找，当前有一个分组
    cout << ans << endl;
}

我真棒！