题解 | #素数伴侣#

将输入的数分为奇数和偶数，只有奇数和偶数的和才有可能为素数，因此需要将奇数集合和偶数集合的数字组合在一起。遍历每一个奇数，为它寻找合适的偶数组成一对，使用find函数，如果合适的偶数已经组成了一对，则让它的奇数同伴寻找其他合适的偶数，如果最终此奇数可以找到偶数组成一对，则组合数加一，循环结束后输出组合对数。

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

bool find(int odd, const vector<int> & evens, vector<int> & evenMatch, vector<int> & used);

int main() {
    int n;
    cin >> n;
    vector<int> evens;
    vector<int> odds;
    int number;
    for (int i = 0; i < n; i++) {
        cin >> number;
        if (number % 2 == 0) {
            evens.push_back(number);
        } else {
            odds.push_back(number);
        }
    }
    vector<int> evenMatch(evens.size(), 0);
    int count = 0;
    for (int odd : odds) {
        vector<int> used(evens.size(), 0);
        if (find(odd, evens, evenMatch, used)) {
            count++;
        }
    }
    cout << count;
    return 0;
}

bool isPrimeNum(int n) {
    if (n == 2) {
        return true;
    }
    for (int i = 2; i < n; i++) {
        if (i * i > n) {
            return true;
        }
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

bool find(int odd, const vector<int> & evens, vector<int> & evenMatch, vector<int> & used) {
    for (int i = 0; i < evens.size(); i++) {
        if (isPrimeNum(odd + evens[i]) && used[i] == 0) {
            used[i] = 1;
            if (evenMatch[i] == 0 || find(evenMatch[i], evens, evenMatch, used)) {
                evenMatch[i] = odd;
                return true;
            }
        }
    }
    return false;
}
// 64 位输出请用 printf("%lld")