题解 | #素数伴侣#

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);
        // 注意 hasNext 和 hasNextLine 的区别
        while(in.hasNext()){
            int size = in.nextInt();
            int[] nums = new int[size];

            List<Integer> odds = new ArrayList<>();
            List<Integer> evens = new ArrayList<>();
            for(int i=0 ; i<size ; ++i){
                nums[i] = in.nextInt();
                if(nums[i] % 2 == 0){
                    evens.add(nums[i]);
                }
                else{
                    odds.add(nums[i]);
                }
            }
            int[] matchEven = new int[evens.size()]; //用于存放匹配的偶数，下标对应偶数的下标，元素为当前下标偶数匹配的奇数
            int count = 0;
            for(int i=0 ; i<odds.size() ; ++i){
                boolean[] v = new boolean[evens.size()];
                if(find(matchEven, v, odds.get(i), evens)){
                    ++count;
                }
            }
            System.out.println(count);
            
        }
    }

    public static boolean isPrime(int num){
        if(num == 1){
            return false;
        }
        for(int i=2 ; i<=Math.sqrt(num) ; ++i){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }

    public static boolean find(int[] matchEven, boolean[] v, int odd, List<Integer> evens){
        for(int i=0 ; i<evens.size() ; ++i){
            if(isPrime(evens.get(i)+odd) && v[i] == false){
                v[i] = true;
                if(matchEven[i] == 0 || find(matchEven, v, matchEven[i], evens)){
                    matchEven[i] = odd;
                    return true;
                }
            }
        }
    return false;
    }
}