题解 | kotori和素因子

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> prime = new ArrayList<>();
        solvePrime(prime);
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            solve(arr[i], lists, prime);
        }
        int[] visited = new int[1005];
        dfs(lists, visited, 0, 0);
        min = min == Integer.MAX_VALUE ? -1 : min;
        System.out.println(min);
    }

    private static void dfs(List<List<Integer>> lists, int[] visited, int index,
                            int currentSum) {
        if (index == lists.size()) {
            if (currentSum < min) {
                min = currentSum;
            }
            return;
        }
        List<Integer> list = lists.get(index);
        for (int i = 0; i < list.size(); i++) {
            if (visited[list.get(i)] == 0) {
                visited[list.get(i)] = 1;
                dfs(lists, visited, index + 1, currentSum + list.get(i));
                visited[list.get(i)] = 0;
            }
        }

    }

    private static void solve(int num, List<List<Integer>> list,
                              List<Integer> prime) {
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < prime.size() && prime.get(i) < num; i++) {
            if (num % prime.get(i) == 0) {
                temp.add(prime.get(i));
            }
        }
        if (prime.contains(num)) {
            temp.add(num);
        }
        list.add(temp);
    }

    private static void solvePrime(List<Integer> prime) {
        for (int i = 2; i <= 1000; i++) {
            boolean isPrime = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                prime.add(i);
            }
        }
    }
}