题解 | #素数伴侣#

import java.util.*;

import java.io.InputStreamReader;

import java.io.BufferedReader;

import java.io.IOException;

import java.util.stream.*;

import java.util.function.*;

public class Main{

//素数伴侣

public static void main(String[] args){

InputStreamReader reader= new InputStreamReader(System.in);
try(BufferedReader br = new BufferedReader(reader)){

    int num = Integer.parseInt(br.readLine());
    String[] numbers_str = br.readLine().split(" ");

    ArrayList<Integer> evens_list = new ArrayList<>(num/2);
    ArrayList<Integer> odds_list = new ArrayList<>(num/2);

    int odd_size=0;
    int even_size=0;

    if (num != numbers_str.length) {
        System.out.println("输入数据错误");
        return;
    }

    //流进行数据类型转换
    List<Integer> numbers_int = Arrays.stream(numbers_str).map(new Function<String, Integer>() {
        @Override
        public Integer apply(String s) {
            return Integer.parseInt(s);
        }
    }).collect(Collectors.toList());



    for (int i = 0; i < numbers_int.size(); i++) {

        if (numbers_int.get(i)%2 == 0) {
               odds_list.add(numbers_int.get(i));
                odd_size++;
        }else   {
            evens_list.add(numbers_int.get(i));
            even_size++;
        }
    }


    //记录奇数
    Integer[] evens =new Integer[even_size];
    evens = evens_list.toArray(evens);
    //记录偶数
    Integer[] odds = new Integer[odd_size];
    odds = odds_list.toArray(odds);
    //记录每个偶数的奇数伴侣
    int[] odd_item = new int[odd_size];

    //记录配对数
    int total=0;
    for (int i = 0; i < evens.length; i++) {
        boolean[] hasMate = new boolean[odd_size];
        if (CanFindMate(evens[i],odds,odd_item,hasMate)) total++;
    }

    System.out.println(total);

}catch(IOException e){
    System.out.print(e.getMessage());
}

}

public static boolean prime(int number){
    if (number % 10 == 5 && number > 5) return false;
    for(int i =2 ; i<= Math.sqrt(number) ; i++){
        if(number % i ==0) return false;
    }
    return true;
}

/*
* now_even 当前奇数
* odds 偶数数组
* odd_item 记录偶数的奇数伴侣 odd_item[i]
* hasMate 记录偶数是否具有奇数伴侣
* */

public static  boolean CanFindMate(int now_even, Integer[] odds , int[] odd_item,boolean[] hasMate){

    for (int i = 0; i < odds.length; i++) {

        // 满足素数 且 当前偶数没有奇数伴侣
        if (prime(now_even + odds[i]) && !hasMate[i]){

            hasMate[i] =true;
            /*
            * odd_item[i] 记录当前偶数的伴侣奇数
            *
            *   1.如果当前偶数没有伴侣奇数（odd_item[i] == 0） 则将当前奇数now_even作为其伴侣
            *   2.如果当前偶数有伴侣（odd_item[i] != 0）
            *       2.1.判断当前偶数（叫B）的伴侣奇数(odd_item[i] 叫A) 是否还具有其它备选的伴侣偶数 CanFindMate(odd_item[i],odds,odd_item)
            *           2.1.1.如果有（叫C）存在A-B A-C： 将当前的偶数作为当前输入的奇数（now_even（叫D））的伴侣      原结果 A-B A-C    重新分配的结果是 A-C D-B
            *           2.1.2.如果没有 仅有A-B： 跳过（给当前now_even（叫D）重新寻找伴侣）
            *
            * */

            if (odd_item[i] == 0 || CanFindMate(odd_item[i],odds,odd_item,hasMate)){
                odd_item[i] = now_even;
                return true;
            }

        }
    }
    return false;
}

}