题解 | #kotori和素因子#

总结：
1.在计算素数时，除数只需要计算到Math.sqrt(n)，不需要遍历到n.而且虽然1不是素因子，但n/1可能是素因子，这种情况应该考虑在内。
2.当将每个整数的因子统计好后，可以使用深度优先搜索，逐层寻找素因子，也可以使用数组统计已被访问过的因子。

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){
                    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;
    }
}