题解 | #素数伴侣#

import java.util.*;

public class Main {
    static Integer numberCount ;
    static List<Integer> oddsList = new ArrayList<>();
    static List<Integer> evensList = new ArrayList<>();
    static Map<Integer, List<Integer>> map = new HashMap<>();
    static int[] matchOdd ; //存偶数x当前匹配的奇数。
    static int[] matchEven; //存奇数x当前匹配的偶数。
    static Map<Integer, Boolean> usedMarkMap = new HashMap<>();// 偶数是否被使用



    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        numberCount = sc.nextInt();
        matchOdd = new int[30001];
        matchEven = new int[30001];
        for (int i = 0; i < numberCount; i++) {
            int num = sc.nextInt();
            if (num % 2 == 0) {
                evensList.add(num);
            } else {
                oddsList.add(num);
            }
        }
        for (int i = 0; i < oddsList.size(); i++) {
            int odd = oddsList.get(i);
            for (int j = 0; j < evensList.size(); j++) {
                Integer even = evensList.get(j);
                if (isPrime(odd + even)) {
                    if (map.get(odd) == null) {
                        List<Integer> list = new ArrayList<>();
                        list.add(even);
                        map.put(odd, list);
                    } else {
                        map.get(odd).add(even);
                    }
                }
            }
        }

        int ans = 0;
        //匈牙利算法
        for (int i = 0; i < oddsList.size(); i++) {
            if (matchOdd[oddsList.get(i)] == 0) {
                usedMarkMap = new HashMap();
                if (dfs(oddsList.get(i))) ans ++;

            }
        }

        System.out.println(ans);
    }

    public static boolean dfs(int odd) {
        for (int i = 0; i < evensList.size(); i++) {
            int even = evensList.get(i);
            if (null != map.get(odd) && map.get(odd).contains(even) ) {
                 if(null == usedMarkMap.get(even)) {
                    usedMarkMap.put(even,true); 
                    if (matchOdd[even] == 0 || dfs(matchOdd[even])) {
                        matchEven[odd] = even;
                        matchOdd[even] = odd;
                        return true;
                    }
                }
            }
        }

        return false;
    }

    /**
     * 是否是质数
     * @param param
     * @return
     */
    public static boolean isPrime(Integer param) {
        for (int i = 2; i <= Math.sqrt(param); i++) {
            if (param % i == 0) return false;
        }
        return true;
    }
}