题解 | #素数伴侣#

// 匈牙利算法：先匹配的先得，后配对的如果可以帮原配找到一个新的匹配就能顶替原配位置
// 因为val>=2，所以该题的素数必由奇数+偶数得来
// 第一步：分组，分为偶数和奇数
// 遍历所有奇数，并找到能与之匹配的偶数
// 每一个奇数都可以匹配所有偶数（如果是已被匹配的偶数，只要可以为原配找到替代偶数就仍旧可以匹配）

let n = Number(readline())

let arr = readline().split(' ').map(i => Number(i)), even = [], odd = []

arr.forEach(i => {
    if(i%2==0)even.push(i)
    else odd.push(i)
})

print(getCount(odd, even))

function getCount(odd, even) {
    // 按照偶数的idx,存放与该位置上的偶数匹配上的奇数数值
    let match = new Array(even.length).fill(0), count = 0
    for(let i=0; i<odd.length; i++) { 
        // 每位奇数都可以匹配任意一位偶数（如果是已被匹配的偶数，就替他的原配找到替代的偶数，仍然可以匹配）
        // 对于同一个递归，不能再去找已经匹配了的偶数，used[i]==1表示该位置的偶数已经被匹配了
        let used = new Array(even.length).fill(0) 
        if(matched(odd[i], even, match, used))count++
    }
    return count
}

function matched(o, even, match, used) {
    for(let i=0; i<even.length; i++) {
        if(isPrime(o, even[i]) && used[i]==0) {
            used[i] = 1
            // 没有原配或者可以替原配找到新的替代当前奇数就匹配成功
            if(match[i]==0 || matched(match[i], even, match, used)) {
                match[i] = o
                return true
            }
        }
    }
    return false
}

function isPrime(a, b) {
    let s = a+b
    for(let i=2; i<s; i++) {
        if(s%i==0)return false
    }
    return true
}