题解 | #素数伴侣#
素数伴侣
https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let arr = [];
rl.on("line", function (line) {
arr.push(line);
});
rl.on("close", function () {
let input = arr[1].split(' ');
let odds = []; // 奇数
let evens = []; //偶数
let count = 0;
let v = new Array(100); //标记访问
let match = new Array(100); //标记与偶数链接的奇数
//判断是否为质数
function isPrime(num) {
if (num < 2) {
return false;
}
for (let i = 2; i*i <=num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
//判断是否匹配
function isMatch(odd) {
let evenLength = evens.length;
for (let i = 0; i < evenLength; i++) {
let sum = Number(odd)+Number(evens[i])
if (isPrime(sum) && !v[i]) {
//有边，未访问，标记
v[i] = true;
//偶数未有匹配的奇数 或者右边有匹配
if (!match[i] || isMatch(match[i])) {
match[i] = odd;
return true;
}
}
}
return false;
}
//执行
function init() {
//1.分奇数偶数
//标记偶数是否匹配的对象
input.forEach((c) => {
if (c % 2 == 0) {
evens.push(c);
} else {
odds.push(c);
}
});
// 2.遍历奇数
let oddLength = odds.length; //zuo
for (let i = 0; i < oddLength; i++) {
v = new Array(evens.length);
let falg = isMatch(odds[i]);
if (falg) {
count++;
}
}
console.log(count);
}
init()
});
查看14道真题和解析