题解 | #素数伴侣#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int[] ints = new int[i];
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for (int j = 0; j <i; j++) {
            ints[j]=scanner.nextInt();
            if (ints[j]%2==0){
                even.add(ints[j]);
            }else {
                odd.add(ints[j]);
            }
        }
        int[] match = new int[even.size()];//下标对应已经匹配的偶数的下标，值对应这个偶数的伴侣
        int count=0;
        for (int j = 0; j < odd.size(); j++) {
            boolean[] ifpped= new boolean[even.size()];//标记对应该奇数是否匹配过每一个偶数
            if(success(odd.get(j),even,match,ifpped)){
                count++;
            }
        }
        System.out.println(count);
    }
    public static boolean success(int odd,ArrayList<Integer> even,int[] match,boolean[] ifpped){
        for (int i = 0; i < even.size(); i++) {
            if (isPrime(odd+even.get(i))&&ifpped[i]==false){
                ifpped[i]=true;
                if(match[i]==0||success(match[i],even, match,ifpped)){//如果当前偶数没有伴侣或偶数有的奇数伴侣可以找到其他偶数伴侣
                    match[i]=odd;
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }
        //判断一个数能否被小于sqrt(n)的数整除
        int sqrt = (int)Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}