题解 | #素数伴侣#

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

public class Main {
    public static void main(String[] args) {
        // TODO: 22/4/16/0016 素数伴侣
        // 1
        Scanner scanner = new Scanner(System.in);
        int maxNumber = scanner.nextInt();
        // 奇数
        List<Integer> odds = new ArrayList<>(maxNumber);
        // 偶数
        List<Integer> evens = new ArrayList<>(maxNumber);
        for (int i = 0; i < maxNumber; i++) {
            int nextInt = scanner.nextInt();
            if (nextInt % 2 == 0) {
                evens.add(nextInt);
            } else {
                odds.add(nextInt);
            }
        }

        int count = 0;
        // matchEvens 用于记录匹配的偶数的下标，下标是匹配的偶数的下标，值是奇数
        int[] matchEvens = new int[evens.size()];
        for (int i = 0; i < odds.size(); i++) {
            boolean[] booleans = new boolean[evens.size()];
            if (findMatch(odds.get(i), matchEvens, evens, booleans)) {
                count++;
            }
        }
        System.out.println(count + "");

    }

    /**
     * 查找俩个数是否匹配
     *
     * @param odd        奇数
     * @param matchEvens 用于记录匹配的偶数的下标，下标是匹配的偶数的下标，值是奇数
     * @param evens      偶数集合
     * @param booleans   是否在当前位置已经匹配
     * @return true：匹配；false:不匹配
     */
    private static boolean findMatch(int odd, int[] matchEvens, List<Integer> evens, boolean[] booleans) {
        for (int i = 0; i < evens.size(); i++) {
            if (isPrime(odd + evens.get(i)) && !booleans[i]) {
                booleans[i] = true;
                if (matchEvens[i] == 0 || findMatch(matchEvens[i], matchEvens, evens, booleans)) {
                    matchEvens[i] = odd;
                    return true;
                }
            }
        }
        return false;
    }

    // 2 判断是不素数数:能被2或者这个数的开平方整除的都不是素数
    private static boolean isPrime(int prime) {
        if (prime == 1) return false;
        for (int i = 2; i <= (int) Math.sqrt(prime); i++) {
            if (prime % i == 0) {
                return false;
            }
        }
        return true;
    }
}