题解 | #素数伴侣#

#include <iostream>
#include <vector>

using namespace std;

bool is_prime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i < num + 1; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

/**
 *
 * @param num 男生
 * @param even 女生数组
 * @param used 女生是否被选过
 * @param match 女生i匹配的男友
 * @return
 */
bool find(int num, vector<int>& even, vector<bool>& used, vector<int>& match) {
    for (int i = 0; i < even.size(); ++i) {
        if (is_prime(num + even[i]) && !used[i]) {
            used[i] = true;
            if (match[i] == 0 || find(match[i], even, used, match)) {
                match[i] = num;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> num(n);
        vector<int> odd;
        vector<int> even;
        for (int i = 0; i < n; ++i) {
            cin >> num[i];
            if (num[i] % 2 == 0) even.push_back(num[i]);
            else odd.push_back(num[i]);
        }
        int count = 0;
        if (odd.size() == 0 || even.size() == 0) {
            cout << count << endl;
            continue;
        }

        vector<int> match(even.size(), 0);
        for (int i = 0; i < odd.size(); ++i) {
            vector<bool> used(even.size(), false);
            if (find(odd[i], even, used, match)) {
                count++;
            }
        }
        cout << count << endl;

    }
    return 0;
}