题解 | #素数伴侣#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // 输入数据
    const n = parseInt(await readline());
    const nums = (await readline()).split(" ").map(Number);
    const odds = nums.filter((item) => item % 2),
        evens = nums.filter((item) => item % 2 === 0);
    // 判断素数
    const isPrime = (num) => {
        const n = Math.floor(Math.sqrt(num))+1;
        for (let i = 2; i < n; i++) {
            if (num % i === 0) return false;
        }
        return num != 1;
    };
    // 匈牙利算法
    const find = (odd, evens, evenMatch, match) => {
        for (let i = 0; i < evens.length; i++) {
            const even = evens[i];
            // 如果这个偶数未被占用，并且和奇数的和是素数
            if (!match[i] && isPrime(even + odd)) {                
                match[i] = true;// 标记这个偶数已被占用
                // 如果这个偶数没有伴侣，或者它的伴侣可以换一个其他的偶数
                if (
                    evenMatch[i] === 0 ||
                    find(evenMatch[i], evens, evenMatch, match)
                ) {                    
                    evenMatch[i] = odd;// 更新这个偶数的伴侣为当前的奇数
                    return true;
                }
            }
        }
        return false;
    };

    //计算结果
    const calculate = () => {
        const evenMatch = new Array(evens.length).fill(0); //记录每个偶数的伴侣奇数
        let cnt = 0;
        // 对每个奇数进行匹配操作
        for (const odd of odds) {
            const match = new Array(evens.length).fill(false); // 创建一个数组，记录每个偶数是否已被占用
            if (find(odd, evens, evenMatch, match)) {
                cnt++; // 如果找到了素数伴侣，就增加计数
            }
        }
        return cnt;
    };
    console.log(calculate());
})();