题解 | #素数伴侣#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class Main {
    private static Map<Integer, Integer> maxMatch = new HashMap<>(); // 最大匹配
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = "";
        while ((str = reader.readLine()) != null) {
            final int n = Integer.parseInt(str);
            final String[] nums = reader.readLine().split(" ");
            List<Integer> odds = new ArrayList<>(); // 奇数组
            List<Integer> evens = new ArrayList<>(); // 偶数组
            for (int i = 0; i < n; i++) {
                final int anInt = Integer.parseInt(nums[i]);
                if (anInt % 2 == 0) evens.add(anInt);
                else odds.add(anInt);
            }
            int[] matching = new int[evens.size()]; // 记录匹配了偶数的奇数
            int count = 0;
            for (int i = 0; i < odds.size(); i++) {
                int[] bematched = new int[evens.size()]; // 记录偶数是否被匹配了，0没匹配，1匹配了
                if (dfs(evens, odds.get(i), matching, bematched)) count++;
            }
            System.out.println(count);
        }
 
        reader.close();
    }
 
    /**
     * @param evens 偶数组
     * @param odd 当前奇数
     * @param matching 由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。
     * @param bematched 记录哪个偶数被匹配了
     * @return 是否能找到新的偶数和当前奇数配对，即能否找到增广路径
     */
    public static boolean dfs(List<Integer> evens, int odd, int[] matching, int[] bematched){
        for (int i = 0; i < evens.size(); i++) {
            // 遍历偶数组，与当前奇数相加是否是素数，即能否匹配成功，同时该偶数还没有被匹配过
            if (isPrime(evens.get(i) + odd) && bematched[i] == 0){
                // 能匹配成功，那这个偶数就要记录下被匹配了
                bematched[i] = 1;
                // 当这个奇数还没有匹配过偶数，这是第一次，那就把这个奇数也记录下来，与当前偶数配对
                // 或者这个奇数已经匹配过偶数了，但是还能找到新的偶数和他匹配，那就去找新的偶数，记录在新偶数的名下吧
                if (matching[i] == 0 || dfs(evens, matching[i], matching, bematched)){
                    matching[i] = odd;
                    maxMatch.put(odd, evens.get(i));
                    return true;
                }
            }
        }
        return false;
    }
 
    /**
     * 判断是否是素数
     * @param n
     * @return
     */
    public static boolean isPrime(int n){
        if (n == 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}