题解 | #素数伴侣#

#include <bits/stdc++.h>

using namespace std;

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

bool find(int num, vector<int> evens, vector<bool>& used, vector<int>& match){
    for(int i = 0; i < evens.size(); i++){//遍历每个偶数与奇数比较
        if(isPrime(num + evens[i]) && !used[i]){
            used[i] = true;
            //如果第i个偶数还未配对，或者跟它配对的奇数还有别的选择
            if(match[i] == 0 || find(match[i], evens, used, match)){ 
                match[i] = num; //则配对该数
                return true;
            }
        }
    }
    
    return false;
}

int main(){
    int n = 0;
    cin >> n;
    vector<int> nums(n);
    vector<int> odds; //奇数数组
    vector<int> evens; //偶数数组
    
    for(int i = 0; i < n; i++){
        cin >> nums[i];
        if(nums[i] % 2 != 0) odds.push_back(nums[i]); //奇数数组
        else evens.push_back(nums[i]); //偶数数组
    }
    
    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(odds[i], evens, used, match)){  //能否找到配对的偶数
                count++;
            }
        }

        cout << count << endl;
    }
    
    
    
    return 0;
}