题解 | #素数伴侣#

借鉴了别人的解题思路。

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

// 判断一个数是否是素数
bool isPrime(int num) {
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

// 寻找素数伴侣 匈牙利算法 递归
bool find_prime(int odd, vector<int> &evens, vector<bool> &used, vector<int> &match) {
    // 对于传入的奇数，遍历每个偶数，进行比较
    for (int i = 0; i < evens.size(); i++) {
        // 如果奇数加偶数为素数，且这个偶数没有被使用过，则检查match数组
        if (isPrime(odd + evens[i]) && !used[i]) {
            used[i] = true;
            if (match[i] == 0 || find_prime(match[i], evens, used, match)) {
                match[i] = odd;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n = 0;
    cin >> n;
    vector<int> odds;   // 奇数
    vector<int> evens;  // 偶数
    for (int i = 0; i < n; i++) {
        int temp = 0;
        cin >> temp;
        if (temp % 2 == 0) evens.push_back(temp);
        else odds.push_back(temp);
    }
    
    int count = 0;   // 统计个数
    if (odds.size() == 0 || evens.size() == 0) {
        cout << count << endl;
    } else {
        vector<int> match(evens.size(), 0);     // 用于统计每个偶数的配对
        for (int i = 0; i < odds.size(); i++) {
            vector<bool> used(evens.size(), false);   // 用于统计每一轮奇数中，偶数是否使用过
            if (find_prime(odds[i], evens, used, match)) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}