题解 | kotori和素因子

//这个思路很直接
import java.util.*;
public class Main {
    public static  int min = 65535;
    private static List<List<Integer>> list = new
    ArrayList<>();//记录每个数的素因子集合
    private static Set<Integer> hash = new
    HashSet<>();//用于统计被访问过的素因子。
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = Integer.valueOf(sc.nextLine());
        String[] num = sc.nextLine().split(" ");


        for (String s : num) {
            int n = Integer.valueOf(s);
            List<Integer> k = new ArrayList<>();
            for (int i = 1; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    // 有2个因子,分别为i和n/i
                    if (isPrime(i)) {
                        k.add(i);
                    }
                    if (isPrime(n / i)) {
                        k.add(n / i);
                    }
                }
            }
            list.add(k);
        }
        dfs(0);
        if (min == 65535)
            System.out.println(-1);
        else
            System.out.println(min);
    }
    public static void dfs(int deepth) {
        if (deepth == list.size()) {
            int add = 0;
            for (int a : hash) {
                add += a;
            }
            min = Math.min(min, add);
            return;
        }
        int size = list.get(deepth).size();
        for (int j = 0; j < size; j++) {
            int e = list.get(deepth).get(j);
            if (hash.contains(e))
                continue;
            hash.add(e);
            dfs(deepth + 1);
            hash.remove(e);
        }

    }
    public static boolean isPrime(int n) {
        if (n == 1)
            return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}