题解 | #素数伴侣#

/**
 * 匈牙利算法，递归
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String a, b;
        try {
            a = r.readLine();
            b = r.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        char[] ch1 = a.toCharArray();
        char[] ch2 = b.toCharArray();
        int i = 0, j = 0, n = 0, num = 0, n0 = 0, n1 = 0, ans = 0;
        do {//数据的个数n
            n = n * 10;
            n += ch1[i] - '0';
            i++;
        } while (i < ch1.length);
        int[] nums = new int[n];//长度为n
        int[] end1 = new int[100];
        int[] end0 = new int[100];
        i = 0;
        do {//生成数据数组
            if (ch2[i] == ' ') {
                nums[j++] = num;
                num = 0;
                i++;
                continue;
            }
            num = 10 * num;
            num += ch2[i] - '0';
            if (i == ch2.length - 1) nums[j] = num;
            i++;
        } while (i < ch2.length);
        i = 0;
        do {//将数据分成奇数和偶数
            num = nums[i];
            if ((num & 1) == 1) end1[n1++] = num;
            else end0[n0++] = num;
            i++;
        } while (i < n);
        if (n0 == 0 || n1 == 0) {//奇数或偶数个数为0，全为奇数或者偶数，素数伴侣0对
            System.out.print(0);
            return;
        }
        i = 0;
        int[] match = new int[n0];//偶数的素数伴侣
        do {//遍历奇数
            int[] used = new int[n0];//该偶数是否被匹配过
            if (find(end1[i], end0, used, match)) ans++;//能找到就表示有一对素数伴侣
            i++;
        } while (i < n1);
        System.out.print(ans);
    }

    //判断是不是素数，是素数为true，不是素数为false
    public static boolean prime(int inNum) {
        if (inNum <= 5) return inNum != 4;//该数小于等于5，只有4不是素数
        int div = inNum % 6;
        if (div != 1 && div != 5) return false;
        int i = 5, j = inNum / 2;
        boolean res = true;
        do {
            if (inNum % i == 0 || (i + 2 != inNum && inNum % (i + 2) == 0)) {//能被5整除，能被除它自身的i+2整除
                res = false;//不是素数
                break;
            }
            i += 6;
        } while (i < j);
        return res;
    }

    //匈牙利算法，先到先得，能让就让
    public static boolean find(int odd, int[] evens, int[] used, int[] match) {
        int m = 0;
        boolean b = false;
        do {
            if (prime(evens[m] + odd) && used[m] == 0) {//该偶数和传入奇数能匹配
                used[m] = 1;//表示该偶数已被一个奇数用了，进行标识
                if (match[m] == 0 || find(match[m], evens, used, match)) {//先到先得，能让就让
                    match[m] = odd;
                    b = true;//能匹配
                    break;
                }
            }
            m++;
        } while (m < used.length);
        return b;
    }
}