按组枚举

思路：
按组为单位来枚举，

1. 如果当前组能填充下一个元素， 就填充下一个元素

2. 如果当前组不能填充下一个元素， 就新建一个组

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 11, min = Integer.MAX_VALUE, n, ans;
    static int[] a = new int[N];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) throws Exception{
        n = Integer.valueOf(read.readLine());
        ans = n; //最多每个数字为一组
        String[] ss = read.readLine().split(" ");
        List[] lists = new List[N];
        for(int i = 0; i < n; i++){
            a[i] = Integer.valueOf(ss[i]);
            lists[i] = new ArrayList();
        }
        dfs(0, 1, lists, 0);

        System.out.println(ans);
    }
    /**
     * 按组为单位来枚举， 
     * 1. 如果当前组能填充下一个元素， 就填充下一个元素
     * 2. 如果当前组不能填充下一个元素， 就新建一个组
     */
    public static void dfs(int start, int groupId, List[] group, int totalCnt){
        if(groupId >= ans) return;
        if(totalCnt == n) ans = groupId;

        boolean add = false;
        for(int i = start; i < n; i++){
            if(st[i]) continue;
            if(check(group[groupId], a[i])){
                st[i] = true;
                group[groupId].add(a[i]);

                dfs(i + 1, groupId, group, totalCnt + 1);

                group[groupId].remove(group[groupId].size() - 1);
                st[i] = false;
                add = true;
            }
        }

        if(!add) dfs(0, groupId + 1, group, totalCnt);
    }

    public static boolean check(List<Integer> list, int b){
        for(Integer a: list){
            if(gcd(a, b) > 1) return false;
        }
        return true;
    }

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