题解 | #素数伴侣#

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
bool isPrime(int n)
{
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0) return false;
    }
    return true;
}
bool check(int n,vector<int>& even,vector<int>& match,vector<bool>& used)
{
    for(int i=0;i<even.size();i++)
    {
        if(isPrime(n+even[i]) && !used[i])
        {
            used[i]=true;
            if(!match[i]||check(match[i],even,match,used))
            {
                match[i]=n;
                return true;
            }
        }
    }
    return false;
}
int main(int argc,char* argv[])
{
    int n;
    while(cin>>n)
    {
        int value;
        vector<int> odd;//奇数
        vector<int> even;//偶数
        while(n--)
        {
            cin>>value;
            if(value%2==0) even.push_back(value);
            else odd.push_back(value);
        }
        int count=0;
        if(odd.size()==0 || even.size()==0)
        {
            cout<<count<<endl;
            continue;
        }
        vector<int> match(even.size(),0);
        for(int i=0;i<odd.size();i++)
        {
            vector<bool> used(even.size(),false);
            if(check(odd[i],even, match, used)) count++;
        }
        cout<<count<<endl;
    }
    return 0;
}