题解 | #素数伴侣#

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

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

bool find(int index, vector<bool>& used, vector<int>& match, vector<vector<bool>>& map){
    for(int i = 0; i < used.size(); ++i){
        if(map[i][index] && !used[i]){
            used[i] = true;
            if(match[i] == -1 || find(match[i], used, match, map)){
                match[i] = index;
                return true;
            }
        }
    }
    return false;
}

int main(int argc, char* argv[]){
    int n;
    cin >> n;
    vector<int> odds;
    vector<int> evens;
    for(int i = 0; i < n; ++i){
        int num = 0;
        cin >> num;
        if(num % 2){
            odds.push_back(num);
        }
        else{
            evens.push_back(num);
        }
    }
    if(odds.empty() || evens.empty()){
        cout << 0 << endl;
        return 0;
    }
    vector<vector<bool>> map(evens.size(), vector<bool>(odds.size(), false));
    for(int i = 0; i < evens.size(); ++i){
        for(int j = 0; j < odds.size(); ++j){
            if(isPrimeNumber(evens[i] + odds[j])){
                map[i][j] = true;
            }
        }
    }
    int count = 0;
    vector<int> match(evens.size(), -1);
    for(int i = 0; i < odds.size(); ++i){
        vector<bool> used(evens.size(), false);
        if(find(i, used, match, map)){
            ++count;
        }
    }
    cout << count;

    return 0;    
}