题解 | #素数伴侣#

#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>

int count = 0, n, num;
// 记录奇数和偶数的数组，对每个偶数去找能够匹配的奇数
vector<int> evens, ods; 
// 记录od是否被访问过的数组。
vector<bool> odIsVisited;
// 记录当前od匹配的even。 原本用字典存的话，如果出现重复奇数的情况，计算结果会出错。
vector<int> odAndEven;

// 判断二者之和是否是素数。
bool isSushu(int a, int b) {
    int num = a + b;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

// 成功匹配的话返回true，否则返回false
bool dfs(int even) {
    // 遍历所有的奇数，看能否匹配。
    for (int i = 0; i < ods.size(); i++) {
        int od = ods[i];
        // 如果能够组成素数，那么可以匹配, 继续判断。
        if (isSushu(even, od) && !odIsVisited[i]) {
            // 如果该奇数访问过，那么跳过。
            odIsVisited[i] = 1; // 标记，表示已经访问过。
            if ( !odAndEven[i] || dfs(odAndEven[i]) ) {
                odAndEven[i] = even;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n;
    while (cin >> num) {
        // cout << num;
        if (num % 2 == 0) {
            evens.push_back(num);
        } else {
            ods.push_back(num);
        }
    }

    odIsVisited.resize(ods.size());
    odAndEven.resize(ods.size());
    fill(odAndEven.begin(), odAndEven.end(), 0);
    // 遍历evens，找ods进行匹配。如果两者相加是素数，则可以配对。
    for (int even : evens) {
        // 每次都初始化odIsVisited为false。表示所有od都没访问过。
        fill(odIsVisited.begin(), odIsVisited.end(), false);
        // 如果even找到了能匹配的ods，则count++. 显然dfs返回bool类型。
        if( dfs(even) ) count++;
    }
    cout << count;

    return 0;
}