题解 | #素数伴侣#

const rl = require("readline").createInterface({ input: process.stdin });

let total = 0;
rl.on("line", (line) => {
    if (total === 0) {
        total = +line;
    } else {
        const oddArr = []; // 存放奇数
        const evenArr = []; // 存放偶数
        line.split(" ").forEach((n) => {
            n % 2 === 0 && evenArr.push(+n);
            n % 2 !== 0 && oddArr.push(+n);
        });

        console.log(getRes(oddArr, evenArr));
    }
});

/**
 * @param oddArr 奇数数组
 * @param evenArr 偶数数组
 * */
function getRes(oddArr = [], evenArr = []) {
    const matchArr = new Array(evenArr.length).fill(0);
    
    // 循环奇数
    for (let i = 0; i < oddArr.length; i++) {
        const used = new Array(evenArr.length).fill(0);
        find(oddArr[i], evenArr, used, matchArr);
    }

    return matchArr.filter((o) => o !== 0).length;
}

/**
 * @param oddNum 奇数
 * @param evenArr 偶数数组
 * @param used 标记配对上的偶数
 * @param matchArr 存放匹配上的的奇数
 * */
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; // 如果配对上就在偶数所在位置打上标记

            // 如果偶数的位置上没有奇数，直接赋值，如果有就让它挪位置
            if (matchArr[i] === 0 ||find(matchArr[i], evenArr, used, matchArr)) {
                matchArr[i] = oddNum;
                return true;
            }
        }
    }
    return false;
}

/* 判断是否是素数 */
function isPrime(num) {
    if (!num || num === 1) return false;

    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) return false;
    }

    return true;
}