题解 | #素数伴侣#

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   public static void main(String[] args){
        //标准输入
        Scanner in=new Scanner(System.in);
        int size = in.nextInt();
        List<Integer> oddList = new ArrayList();
        List<Integer> evenList = new ArrayList();
        for (int i = 0; i < size; i++) {
            int a = in.nextInt()  ;
            if (a % 2 == 1) {
                oddList.add(a);
            } else {
                evenList.add(a);
            }
        }
        int count = 0;
        //用于储存已经约定好的对应的匹配值
        int[] macthevens = new int[evenList.size()];
        for(int i = 0; i < oddList.size(); i++){
            //需要寻求匹配的奇数
            int oddData = oddList.get(i);
            boolean[] recordData = new boolean[evenList.size()];
            if(isMatch(oddData,evenList,macthevens,recordData)){
                count++;
            }
        }

        System.out.println(count);
    }


    private static boolean isMatch(int oddData, List<Integer> evenList,int[] macthevens,boolean[] recordData){
        for(int j = 0; j < evenList.size(); j++){
            if(isPrime(oddData+evenList.get(j)) && !recordData[j]){
                //如果成功设值，说明数据已经被使用
                recordData[j] = true;
                //当对应的even数据还没有匹配奇数则直接将数据匹配
                //当数据已经有匹配的情况，查看数据是否能够让出来，可以让出来则直接让出来，原先的匹配数据再从新去匹配
                if(macthevens[j] == 0 || isMatch(macthevens[j],evenList,macthevens,recordData)){
                    macthevens[j] =oddData;
                    return true;
                }
            }
        }
        return false;
    }



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


}