题解 | #素数伴侣#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] nums = new int[n];
            for(int i=0;i<n;i++){
                nums[i] = sc.nextInt();
            }
            ArrayList<Integer> evens = new ArrayList<>();
            ArrayList<Integer> odds = new ArrayList<>();

            for(int i=0;i<n;i++){
                if((nums[i]&1)==1){
                    odds.add(nums[i]);
                }else{
                    evens.add(nums[i]);
                }
            }
            int[] evensMatch = new int[evens.size()];
            int count = 0;
            for(int i=0;i<odds.size();i++){
                int[] used = new int[evens.size()];
                if(find(used,evens,odds.get(i),evensMatch)){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static boolean isPrime(int num){
        for(int i=2;i*i<=num;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }

    public static boolean find(int[] used,ArrayList<Integer> evens,int num,int[] evensMatch){
        for(int i=0;i<evens.size();i++){
            if(isPrime(num+evens.get(i))&&used[i]==0){
                used[i]=1;
                //第二个条件相当于回溯，新的奇数要匹配这个偶数，但是这个偶数已经被旧的奇数占用了
                //那么就让旧的奇数再去找一个新的匹配结果，used保证了不会重复冲突
                if(evensMatch[i]==0||find(used,evens,evensMatch[i],evensMatch)){
                    evensMatch[i] = num;
                    return true;
                }
            }
        }
        return false;
    }

}