题解 | 素数伴侣

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

bool isprime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }//除去2和3，质数必为6k+1或6k-1的形式，非2，3倍数的其他这类6k+-1的数只要不是比它小的质数的倍数即可，并且只用检查到根号n。
    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;
            if(match[i] == 0 || find(match[i], evens, used, match)){ //如果第i个偶数还未配对，或者跟它配对的奇数还有别的选择
                match[i] = num; //则配对该数
                return true;
            }
        }
    }
    return false;
}
int main(){
    int n;
    while(cin >> n){
        vector<int> odds;
        vector<int> evens;
        vector<int> nums(n);
        for(int i = 0; i < n; i++){ //输入n个数
            cin >> nums[i];
            if(nums[i] % 2) //奇数
                odds.push_back(nums[i]);
            else //偶数
                evens.push_back(nums[i]);
        }
        int count = 0;
        if(odds.size() == 0 || evens.size() == 0){ //缺少奇数或者偶数无法构成素数
            cout << count << endl;
            continue;
        }
        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;
}

抄的，记得多看看