题解 | #kotori和素因子#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //默认不存在栈深为n（正整数个数）的路径
    public static int min = Integer.MAX_VALUE;
    //记录每个数的素因子集合
    private static final List<List<Integer>> list = new ArrayList<>();
    //用于标记访问过的素因子（一条路径上）
    private static final Set<Integer> set = new HashSet<>();

    //判素数模板
    public static boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        st.nextToken();
        int n = (int) st.nval;
        for (int i = 0; i < n; i++) {
            st.nextToken();
            int num = (int) st.nval;
            //存储每个数的素因子集合
            list.add(getPrimes(num));
        }
        dfs(0, 0);
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    private static void dfs(int depth, int sum) {
        //在每个素因子集合中选出一个组成一条包含不同素因子的路径，就求一次和
        if (depth == list.size()) {
            min = Math.min(min, sum);
            return;
        }
        int size = list.get(depth).size();
        for (int i = 0; i < size; i++) {
            int e = list.get(depth).get(i);
            if (set.contains(e)) continue;
            set.add(e);
            dfs(depth + 1, sum + e);
            //下层递归完，返回上一层，将已经标记过的移出路径
            set.remove(e);
        }
    }

    //获取整数的素因子集合
    private static List<Integer> getPrimes(int num) {
        List<Integer> p = new ArrayList<>();
        for (int i = 1; i < Math.sqrt(num); i++) {
            if (num % i == 0) {
                if (isPrime(i)) p.add(i);
                if (isPrime(num / i)) p.add(num / i);
            }
            //有平方根的整数的平方根项要单独判断，否则会出现9 {3，3} 这样重复的素因子，极大降低性能。
            double c = Math.sqrt(num);
            if (Math.floor(c) == c) {
                if (isPrime((int) c))
                    p.add((int) c);
            }
        }
        return p;
    }
}