题解 | #素数伴侣#

//搬运隔壁java高赞答案
//素数不是偶数，一定是奇数 +偶数
// 判断奇数 ，偶数，素数可拆分为子函数
// 求最大的配对采用匈牙利算法，基本思想是：先配对的先得，后配对的能让就让，让不了时就是最大配对数


//判断素数的函数
function isPrime(num){
    
    if (!num) return false;
    if (Number(num) == 1 ) return false;
    for (let i =2; i*i <=num;i++ ){
        if (num % i == 0){
            return false;
        }
    }
    return true;
}
//console.log(isPrime(6));

//传入每一轮输入的偶数和奇数序列
function getRes(oddArr,evenArr){
//构造matchArr用于存放和偶数序列能配对的奇数的值，不是下标    
    let matchArr = new Array(evenArr.length).fill(0);
// count存放能配对的奇数个数    
    let count =0;    
//循环奇数
    for(let i =0; i<oddArr.length;i++){
        //构造used存放能偶数是否已经配对，记录已经配对的下标，重点是每次奇数遍历需重置，递归时不重置
        //可以理解对每个新传去的奇数来说，所有偶数都是潜在对象，当对递归的原配奇数来讲，不能再去配对已经配对的偶数
        let used = new Array(evenArr.length).fill(0);
        if (find(oddArr[i],evenArr,used,matchArr)){
            count++;
        }
    }
    console.log(count);
}

//重头戏 匈牙利算法
function  find (oddnum,evenArr,used,matchArr){
    for(let i =0; i<evenArr.length; i++){  //循环每个偶数与传入的奇数配对
        if (isPrime(oddnum + evenArr[i])&&(used[i]==0)){ //如果当前偶数与传入的奇数匹配，并且当前偶数位还没有匹配过奇数
            used[i]=1;
//如果第i个偶数没有伴侣
//或者第i个偶数原来有伴侣，并且该伴侣能够重新找到伴侣的话(这里有递归调用)
//则奇数x可以设置为第i个偶数的伴侣
//这里采用了匈牙利算法，能让则让
            if(matchArr[i] == 0 || find(matchArr[i],evenArr,used,matchArr)){
                matchArr[i] = oddnum;
                return true;
            }
        }
    }
//遍历完偶数都没有可以与传入奇数做伴侣的，该奇数只能孤独终老了
//    console.log("break")
    return false;
}



//奇偶区分，程序入口
let totalArr =[];
let line = "";
while (line = readline()){
    totalArr.push(line);
    let tempArr = [];
    if (totalArr.length == 2){
            let evenArr = [];
            let oddArr = [];
        tempArr = totalArr[1].split(" ");
        tempArr.forEach((e)=>{
            if (parseInt(e) % 2 == 0) evenArr.push(parseInt(e))
            if (parseInt(e) % 2 !== 0) oddArr.push(parseInt(e))
        })
        
            totalArr = []; 
 //      console.log(oddArr + "|" + evenArr)
// 将每一轮的奇偶数组传出
         getRes(oddArr,evenArr);
    }
}