题解 | #素数伴侣#

匈牙利算法：两个数列进行配对，对于左列的每个数，让它和右列每个数尝试进行匹配。有如下原则：

1. 先到先得：如果左列中的元素第一次找到匹配成功的右列元素，则配对；
2. 能让则让：如果右列中被匹配到的元素还有其他选择，则让出。

之所以能够使用这个算法，是因为组成素数的两个数必须一奇一偶，否则他们的和就是偶数了，一定不是素数。

首先，将输入数组分为奇数数组和偶数数组。

其次，对于每一个偶数元素，维护一个它的配对数map，元素存放对应下标的偶数所配对成功的奇数下标。

然后，遍历每个奇数，让偶数数列中的每一个数都尝试匹配。如果匹配成功，计数+1.

匹配的函数在判断的同时也更新map：

对每一个偶数和输入的奇数，如果相加是素数，则：

• 判断这个偶数是否已经有配对
• 如果没有配对，则更新map并返回true。
• 如果已经有配对，则检查这个奇数能否和其他偶数匹配：
• 如果可以，就更新map并返回true。
• 如果不可以，不做任何操作。

最后返回false。

由上面的分析可以发现，对于每个奇数，我们需要一个visited数组，记录对应下表的偶数是否在这一轮查找中被访问过。

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

void (async function () {
    // Write your code here
    let n = parseInt(await readline());
    let nums = (await readline()).split(" ").map((x) => parseInt(x));

    let primes = new Set([2, 3, 5, 7, 11, 13]);
    function isPrime(a) {
        if (primes.has(a)) return true;
        for (let i = 2; i < Math.floor(a / 2); i++) {
            if (a % i == 0) {
                return false;
            }
        }
        primes.add(a);
        return true;
    }

    let evens = nums.filter(x => x % 2);
    let odds = nums.filter(x => !evens.includes(x));

    let map = new Array(evens.length).fill(-1); // 存储偶数对应的伴侣下标

    function group(x, visited) {
        for (let i = 0; i < evens.length; i++) {
            if (!visited[i] && isPrime(x + evens[i])) {
                visited[i] = true;
                if (map[i] == -1 || group(map[i], visited)) {
                    map[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

    let cnt = 0;
    for (let i = 0; i < odds.length; i++) {
        let visited = Array(evens.length).fill(false);
        if (group(odds[i], visited)) {
            cnt++;
        }
    }
    console.log(cnt);
})();