题解 | 素数伴侣

import java.util.*;

public class Main {
    // 判断是否为素数
    private static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    // 使用匈牙利算法寻找最大匹配
    private static boolean find(int x, boolean[] used, int[] match, List<Integer> odds, List<Integer> evens) {
        for (int i = 0; i < evens.size(); i++) {
            if (!used[i] && isPrime(odds.get(x) + evens.get(i))) {
                used[i] = true;
                if (match[i] == -1 || find(match[i], used, match, odds, evens)) {
                    match[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 将输入数字分为奇数组和偶数组
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            if (num % 2 == 0) {
                evens.add(num);
            } else {
                odds.add(num);
            }
        }
        
        int[] match = new int[evens.size()];
        Arrays.fill(match, -1);
        int count = 0;
        
        // 对每个奇数尝试匹配
        for (int i = 0; i < odds.size(); i++) {
            boolean[] used = new boolean[evens.size()];
            if (find(i, used, match, odds, evens)) {
                count++;
            }
        }
        
        System.out.println(count);
        sc.close();
    }
}