题解 | #素数伴侣#递归02

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int ok = 0;//记录配对成功的次数

        int num = in.nextInt();
        ArrayList<Integer> oddArr = new ArrayList<Integer>();//奇
        ArrayList<Integer> evenArr = new ArrayList<Integer>();
        //分奇数偶数提取
        for(int i = 0; i< num; i++){
            int temp = in.nextInt();
            if(temp % 2 == 0){
                evenArr.add(temp);
            }else oddArr.add(temp);
        }
        //状态位:even标记配对的是哪个odd 没有配对就是0
        int[] evenState = new int[evenArr.size()];
        //开始配对
        //由于需要递归调用，所以最好写个子函数
        for(int i=0; i<oddArr.size(); i++){
            //每次需要重新定义一个标记量door，防止同一个奇数多次访问相同变量
            int[] door = new int[evenArr.size()];
            //对odd遍历调用find函数，找到一个就ok++;
            if(find(oddArr.get(i), evenArr,evenState,door)){
                ok++;
            }
        }
        System.out.print(ok);
    }

    //素数判断
    public static boolean isPrime(int x, int y){
        int he = x + y;
        for(int i = 2; i <= (int)Math.sqrt(he); i++){
            if(he % i == 0){
                return false;
            }
        }
        return true;
    }
    //奇数配对函数（递归）
    public static boolean find(int odd, ArrayList<Integer> evenArr, int[] evenState ,int[] door){
        //遍历偶数
        for(int i=0; i<evenArr.size(); i++){
            //如果没配过对并且素数，那就配对
            if( isPrime(odd, evenArr.get(i)) && door[i] == 0){
                // evenState[i] = odd;
                door[i] = 1;//标记访问
                if(evenState[i] == 0 || find(evenState[i], evenArr, evenState, door)){
                    evenState[i] = odd;
                    return true;
                }
                
            }
            //如果这个偶数配对过了，去看看他的奇数能不能让出来(没有访问过才可以，不然就会死循环)
            // else if(evenState[i] != 0 && isPrime(odd, evenArr.get(i)) && door[i] == 0){
            //     if(find(evenState[i], evenArr, evenState, door)){
            //         evenState[i] = odd;//能让出来就给他，返回成功
            //         return true;
            //     }
            // }
            //这样做会死循环，必须限制每一个奇数只能对同一个偶数遍历一次，由于主循环遍历每一个奇数，所以只需要加一个访问状态变量
        }
        //找到根都不行那就是不能配对
        return false;

    }
}