题解 | #素数伴侣#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                evens.add(num);
            } else {
                odds.add(num);
            }
        }
        int[] match = new int[evens.size()];
        Arrays.fill(match, -1);
        int count = 0;
        for (int i = 0; i < odds.size(); i++) {
            boolean[] used = new boolean[evens.size()];
            if (find(odds.get(i), evens, used, match)) {
                count++;
            }
        }
        System.out.println(count);
    }

    private static boolean find(int x, List<Integer> evens, boolean[] used,
                                int[] match) {
        for (int i = 0; i < evens.size(); i++) {
            if (isPrime(x + evens.get(i)) && !used[i]) {
                used[i] = true;
                if (match[i] == -1 || find(match[i], evens, used, match)) {
                    match[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}