题解 | #素数伴侣#

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();

        while (count > 0) {
            int next = in.nextInt();
            (next % 2 == 0 ? evens : odds).add(next);
            count--;
        }
        int total = 0;
        Map<Integer, Integer> pairs = new HashMap<>();
        for (int i = 0; i < odds.size(); i++) {
            Set<Integer> checkedSet = new HashSet<>();
            int odd = odds.get(i);
            if (match(odd, evens, pairs, checkedSet)) {
                total++;
            }
        }
        System.out.println(total);
    }

    // 匈牙利算法（为什么贪心能保证是最多的匹配呢？）
    static boolean match(int odd, List<Integer> evens,
                         Map<Integer, Integer> pairs, Set<Integer> checkedList) {
        for (int i = 0; i < evens.size(); i++) {
            int even = evens.get(i);
            // checkedList.contains(even) 非常关键，否则会栈溢出
            if (!checkPrime(odd + even) || checkedList.contains(even)) continue;

            checkedList.add(even);
            if (!pairs.containsKey(even)) {
                pairs.put(even, odd);
                return true;
            }
            if (pairs.containsKey(even)
                    && match(pairs.get(even), evens, pairs, checkedList)) {
                pairs.put(even, odd);
                return true;
            }
        }
        return false;
    }

    static boolean checkPrime(long a) {
        if (a <= 1 ) return false;
        for (int i = 2; i <= a / i; i++) {
            if (a % i == 0) return false;
        }
        return true;
    }
}