题解 | #kotori和素因子#

import java.util.*;

class P {
    static final int limit = (int) 1e4;
    static int size = 0;
    static int[] prime = new int[limit];
    static boolean[] mark = new boolean[limit];
    static Map<Integer, Set<Integer>> meo = new HashMap<>();

    static void init() {
        for (int i = 2; i < limit; i++) {
            if (!mark[i]) {
                prime[size++] = i;
            }
            for (int j = 0; j < size; j++) {
                int it = prime[j];
                if (i * it >= limit) {
                    break;
                }
                mark[i * it] = true;
                if (i % it == 0) {
                    break;
                }
            }
        }
        mark[0] = mark[1] = true;
    }

    static {
        init();
    }


    int num;
    Set<Integer> children;

    P() {
        num = 0;
        children = new HashSet<Integer>();
    }

    P(int num) {
        this.num = num;
        children = new HashSet<>();
        if (meo.containsKey(num)) {
            children = meo.get(num);
            return;
        }
        for (int i = 0; prime[i] <= num; i++) {
            int it = prime[i];
            if (num % it == 0) {
                children.add(it);
            }
        }
        meo.put(num, children);
    }


    @Override
    public String toString() {
        return "P{" + "num=" + num + ", children=" + children + '}';
    }
}

class Solution {
    final int limit = (int) 1e4;
    boolean[] used;
    P[] items;
    int res;

    Solution() {
        res = Integer.MAX_VALUE;
        used = new boolean[limit];
        items = new P[1];
    }

    Solution(int[] arr) {
        int n = arr.length;
        items = new P[n];
        res = Integer.MAX_VALUE;
        used = new boolean[limit];
        for (int i = 0; i < n; i++) {
            items[i] = new P(arr[i]);
        }
        dfs(n - 1, 0);
    }


    void dfs(int n, int sum) {
        if (sum >= res) {
            return;
        }
        if (n == -1) {
            res = sum;
            return;
        }
        for (int it : items[n].children) {
            if (!used[it]) {
                used[it] = true;
                dfs(n - 1, sum + it);
                used[it] = false;
            }
        }
    }

    public int getRes() {
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

public class Main {
    static void solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Solution tool = new Solution(arr);
        System.out.println(tool.getRes());
    }

    public static void main(String[] args) {
        solve();
    }
}