题解 | #素数伴侣#

匈牙利算法
小技巧：偶数与偶数、奇数与奇数的和一定为一个偶数，即能被2整除，肯定不为素数。因此素数只能由奇数加偶数组成。
将奇数、偶数分为两列，寻找素数伴侣即是转化为寻找二部图増广路径。

import java.util.*;
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            ArrayList<Integer> evens = new ArrayList();
            ArrayList<Integer> adds = new ArrayList();

            for (int i = 0; i < n; i++) {
                if ((arr[i] & 1) == 1) {
                    evens.add(arr[i]);
                } else {
                    adds.add(arr[i]);
                }
            }
            int[] evensMatch = new int[evens.size()];
            int count = 0;
            for (int i = 0; i < adds.size(); i++) {
                int[] used = new int[evens.size()];
                if (find(used, evens, adds.get(i), evensMatch))
                    count++;
            }
            System.out.println(count);

        }
    }


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

    public static boolean find(int[] used, ArrayList<Integer> evens, int num, int[] evensMatch) {
        for (int i = 0; i < evens.size(); i++) {
            if (isPrime(num + evens.get(i)) && used[i] == 0) {
                used[i] = 1;
                if (evensMatch[i] == 0 || find(used, evens, evensMatch[i], evensMatch)) {
                    evensMatch[i] = num;
                    return true;
                }
            }
        }
        return false;
    }
}