题解 | #素数伴侣#典型的匈牙利算法---方便自己看

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 获取输入的正整数个数
        int n = in.nextInt();
        // 定义一个集合，用于存放这n个正整数中奇数
        List<Integer> jishu = new ArrayList<>();
        // 定义一个集合，用于存放这n个正整数中的偶数
        List<Integer> oushu = new ArrayList<>();
        // 读取输入的正整数
        for (int i = 0; i < n; i++) {
            int m = in.nextInt();
            if (m % 2 == 0) {
                //偶数
                oushu.add(m);
            } else {
                // 奇数
                jishu.add(m);
            }
        }
        // 查找素数伴侣，返回查找到的最大对数
        int max = findResult(jishu, oushu);
        // 输出最大对数
        System.out.println(max);
    }
    /**
     * 查找n个正整数中存在素数伴侣的最大对数.
     */
    private static int findResult(List<Integer> jishu, List<Integer> oushu) {
        // 定义找到的最大对数
        int max = 0;
        // 定义一个数组，用于存放偶数的伴侣，这个数组里面存放的是奇数列表中的值，默认0填充
        int[] oushuSoul = new int[oushu.size()];
        // 对奇数进行遍历，判断该奇数能否找到偶数伴侣
        for (int i = 0; i < jishu.size(); i++) {
            // 定义一个数组，用于存放偶数列表中的偶数是否被该奇数配对过
            boolean[] isPair = new boolean[oushu.size()];
            // 如果奇数和偶数能够形成最优配对，则max加1
            if (isPairSuccess(jishu.get(i), oushu, oushuSoul, isPair)) {
                max++;
            }
        }
        return max;
    }
    /**
     * 判断奇数 jishu,是否能够在oushu列表中形成最优配对
     */
    private static boolean isPairSuccess(int jishu, List<Integer> oushu,
                                         int[] oushuSoul,
                                         boolean[] isPair) {
        // 将这个奇数依次与偶数进行配对，看是否存在最优配对
        for (int i = 0; i < oushu.size(); i++) {
            // 如果两则相加为素数，切该位置还没有配对过，则可组成素数伴侣，但最优素数伴侣得继续进行条件判断
            if (isPrimeNumber(jishu + oushu.get(i)) && isPair[i] == false) {
                // 将该偶数设置为已配对过
                isPair[i] = true;
                // 匈牙利算法，先到先得，能让就让;如果该位置的偶数还没有奇数伴侣，则形成最佳素数伴侣(先到先得);
                // 如果该位置偶数已经有了奇数伴侣，那么就看这个奇数是否还能找到其他的偶数伴侣，如果能找到，
                // 就将该位置偶数让出(能让就让)
                if (oushuSoul[i] == 0 ||
                        isPairSuccess(oushuSoul[i], oushu, oushuSoul, isPair)) {
                    // 将该位置偶数伴侣添加到数组进行配对成功
                    oushuSoul[i] = jishu;
                    // 找到最优的素数伴侣了
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 判断一个数是否为素数.
     * 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数
     */
    private static boolean isPrimeNumber(int num) {
        for (int i = 2; i < num; i++) {
            // 在2-num之间，只要存在一个数，使得num能被这个数整除，则num为非素数
            if (num % i == 0 ) {
                return false;
            }
        }
        // 上面没有返回false,则表明不存在一个数，使得num能被这个数整除，则num为素数,则返回true
        return true;
    }
}