题解 | #素数伴侣#

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

bool PrimeMate(int x, int y){//判断两个数是不是素数伴侣
    int a = x + y;
    for(int i = 2; i <= sqrt(a); i++){
        if(a % i == 0) return false;;
    }
    return true;
}

bool find(int num, vector<int>& evens, vector<bool>& i_used, vector<int>& match){//对于奇数集合中的一个数num，寻找偶数集合中是否有数能与其配对
    for(int j = 0; j < evens.size(); j++){
        if(PrimeMate(num, evens[j]) && !i_used[j]){
            i_used[j] = true;//当前偶数已经被该基数考虑过
            if(match[j] == -1 || find(match[j], evens, i_used, match)){//当前偶数未配对或所配对的奇数还有其他配对方式
                match[j] = num;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    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) evens.push_back(nums[i]);
        else odds.push_back(nums[i]);
    }
    if(odds.size() == 0 || evens.size() == 0) cout << 0 << endl;//如果所给序列中只有奇数或只有偶数，则没有素数伴侣（除了2之外，所有素数都是奇数）
    else{
        int count = 0;
        vector<int> match(evens.size(), -1);//记录与偶数配对的奇数
        for(int i = 0; i < odds.size(); i++){
            vector<bool> i_used(evens.size(), false);
            if(find(odds[i], evens, i_used, match)) count ++;
        }
        cout << count << endl;
    }
    return 0;
}