题解 | #素数伴侣#

import java.util.*;

public class Main{
    
    public static void main(String [] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            //定义数组
            int [] nums = new int[n];
            for(int i = 0;i < n ;i++){
                nums[i] = in.nextInt();
            }
            //分装为 偶数数组 和奇数数组
            List<Integer> evens = new ArrayList<>();
            List<Integer> odds = new ArrayList<>();
            
            for(int num:nums){
                if(num % 2 ==0){
                    evens.add(num);
                }else{
                    odds.add(num);
                }
            }
            //偶数的伴侣
            int [] evenMatch = new int[evens.size()];
            int count = 0;
            //用每个奇数 尝试匹配偶数
            for(int i = 0;i < odds.size();i++){
                int odd = odds.get(i);
                //偶数是否被占用
                boolean [] match = new boolean[evens.size()];
                if(find(odd,evens,evenMatch,match)){
                    count++;
                }
            }
            System.out.println(count);
            
        }
    }
    
    private static boolean find(int odd,List<Integer> evens,int [] evenMatch,boolean [] match){
        for(int i = 0;i < evens.size();i++){
            int even = evens.get(i);
            //挨个匹配 偶数
            if(!match[i] && isPrime(even + odd)){
                //这个偶数没有被占用 且 偶数+奇数 为素数
                //增加访问标记
                match[i] = true;
                if(evenMatch[i] == 0 || find(evenMatch[i],evens,evenMatch,match)){
                    //偶数索引对应的 素数为0 说明没有被其他素数占用 或者可以找到素数
                    //则将该奇数设置为偶数的伴侣
                    evenMatch[i] = odd;
                    //找到了素数
                    return true;
                }
                
            }
        }
        return false;
    }
    
              
    private static boolean isPrime(int x){
        if(x == 1){
            return false;
        }
        for(int i = 2; i <= (int)Math.sqrt(x);i++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }          
}