题解 | #素数伴侣#

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
             int n = sc.nextInt();
        sc.nextLine();
        ArrayList<Integer> zsList = new ArrayList<Integer>();
        ArrayList<Integer> jList = new ArrayList<Integer>();
        ArrayList<Integer> oList = new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            int num = sc.nextInt();
//             if(isZs(num)){
//                 zsList.add(num);
                if((num & 1)==1){
                    //奇数
                    jList.add(num);
                }else{
                    oList.add(num);
                }
//             }
        }
        int count = 0;
        //存放偶数下标对应的奇数
        int[] oarr = new int[oList.size()];
        for(int j=0;j<jList.size();j++){
            //当前奇数使用过的偶数
            int[] used = new int[oList.size()];
            if(find(jList.get(j),used,oList,oarr)){
                count++;
            }
        }
        System.out.println(count);
        sc.nextLine();
        }
       
    }
    
    private static boolean isZs(int m){
        for(int i=2;i<m;i++){
            if(m%i==0){
                return false;
            }
        }
        return true;
    }
    
    private static boolean find(int js,int[] used,ArrayList<Integer> oList,int[] oarr){
        for(int o=0;o<oList.size();o++){
            if(isZs(oList.get(o)+js)&&used[o]!=1){
                used[o] = 1;
                if(oarr[o]==0||find(oarr[o],used,oList,oarr)){
                    oarr[o] = js;
                    return true;
                }
            }
        }
        return false;
    }
}