本题目采用了匈牙利算法，起初以为只是找到所有的素数伴侣，但是题目有一个条件，那就是每个数字只能使用一次，组成拥有最多的素数伴侣
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
var count = 0
rl.on('line', function (line) {
if(!count)
{
count = Number(line)
} else {
console.log(fn(line.split(' ')))
count = 0
}
});
var fn = (arr) => {
const odds = [] // 存放奇数
const evens = [] // 存放偶数
for(let i in arr) {
if(arr[i] % 2 === 0) {
evens.push(arr[i])
} else {
odds.push(arr[i])
}
}
//用于标记哪个奇数匹配了偶数,直接记录奇数的值
const evensMatch = []
let result = 0
// 遍历奇数去匹配偶数
for(let i in odds) {
// 记录当前的偶数位是否已经匹配了奇数
const used = []
if (find(Number(odds[i]), evens, used, evensMatch)) result ++
}
return result
}
// var fn = (arr) => {
// let result = 0
// const totals = []
// for(let i = 0;i < arr.length;i++) {
// result = 0
// for(let j = i+1;j < arr.length;j++) {
// // 确保是一个基数和一个偶数
// if(Number(arr[i]) % 2 === 0 && Number(arr[j]) % 2 !== 0 || Number(arr[j]) % 2 === 0 && Number(arr[i]) % 2 !== 0) {
// if(isPrem(Number(arr[i]) + Number(arr[j]))) { // 如果找到第一组素数伴侣
// let temp = JSON.parse(JSON.stringify(arr))
// temp.splice(i, 1)
// temp.splice(j, 1)
// result = 1 + fn(temp)
// }
// }
// }
// totals.push(result)
// }
// return Math.max(...totals)
// }
// 判断一个数是否为素数
var isPrem = num => {
// 从2-根号num 在这个范围内有被整除的 那么它就不是素数
const max = Math.sqrt(num)
for(let i = 2; i<=max;i++) {
if(num % i === 0) return false
}
return true
}
var find = (x, evens, used, evensMatch) => {
//遍历偶数
//去检查当前传入的奇数能否与偶数哪些数匹配
for(let i in evens) {
// 如果当前偶数与传入的奇数匹配，并且当前偶数位还没有匹配过奇数
if(isPrem(x + Number(evens[i])) && !used[i]) {
used[i] = 1
//如果第i个偶数没有伴侣
//或者第i个偶数原来有伴侣，并且该伴侣能够重新找到伴侣的话(这里有递归调用)
//则奇数x可以设置为第i个偶数的伴侣
//这里采用了匈牙利算法，能让则让
if(!evensMatch[i] || find(evensMatch[i], evens, used, evensMatch)) {
evensMatch[i] = x;
return true;
}
}
}
//遍历完偶数都没有可以与传入奇数做伴侣的，该奇数只能孤独终老了
return false
}