# HJ28 素数伴侣

https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e (opens new window)

# 描述

题目描述

若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:

输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。

输入描述：

输入一个正偶数 n
输入 n 个整数

输出描述：

求得的“最佳方案”组成“素数伴侣”的对数。

示例1

输入：
4
2 5 6 13

输出：
2

示例2

输入：
2
3 6

输出：
0

# 难点

如何判断是素数(prime)？
采用二分图、匈牙利算法查找最优组合

# 如何判断是素数(prime)？

质数又称素数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数

0 和 1 既不是质数也不是合数，最小的质数是 2

偶数 + 偶数 = 合数

奇数 + 奇数 = 合数

奇数 + 偶数有可能是质数（素数）

function isPrime(num) {
  if (num <= 1) {
    return false;
  }

  const max = Math.sqrt(num);

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

  return true;
}

# 采用二分图、匈牙利算法查找最优组合

。。。

# 解答

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

void (async function () {
    let line;
    let lines = [];
    while ((line = await readline())) {
        lines.push(line);
    }

    const nums = lines[1].split(" ").map((item) => parseInt(item));
    const oddNums = []; // [1, 3, 5, ...]
    const evenNums = []; // [2, 4, 6, 8, ...]

    for (let i = 0, len = nums.length; i < len; i++) {
        const num = nums[i];
        if (num % 2 === 0) {
            evenNums.push(num);
        } else {
            oddNums.push(num);
        }
    }

    let count = 0;
    const matchedOdds = [];

    for (let i = 0, len = oddNums.length; i < len; i++) {
        const oddNum = oddNums[i];
        const usedEvenNums = [];

        if (matchEven(oddNum, evenNums, usedEvenNums, matchedOdds)) {
            count += 1;
        }
    }

    console.log(count);
})();

function matchEven(oddNum, evenNums, usedEvenNums, matchedOdds) {
    for (let i = 0, len = evenNums.length; i < len; i++) {
        const evenNum = evenNums[i];
        const sum = oddNum + evenNum;
        const isPrimeNum = isPrime(sum);

        // 和 不是素数
        if (!isPrimeNum) {
            continue;
        }

        // 和 是素数


        // 该偶数 没有匹配过
        if (usedEvenNums[i]) {
            continue;
        }

        usedEvenNums[i] = true;

        const matchedOdd = matchedOdds[i];

        // 该偶数没有匹配的奇数
        if (!matchedOdd) {
            matchedOdds[i] = oddNum;
            return true;
        }

        // 该偶数有匹配的奇数

        // 如果 已经匹配的奇数 有额外的匹配，则 已经匹配的奇数 腾位置给当前奇数
        if (matchEven(matchedOdd, evenNums, usedEvenNums, matchedOdds)) {
            matchedOdds[i] = oddNum;
            return true;
        }
    }

    return false;
}

function isPrime(num) {
    if (num <= 1) {
        return false;
    }

    const max = Math.sqrt(num);

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

    return true;
}

# 参考

本章目录