代码基本上参考了博客[1]，内含原理阐释。我实现的判断素数算法，减少for循环运行的次数，运行速度较快。

#include <iostream>
#include <math.h>
#include <vector>
#include <memory.h>
using namespace std;
static inline bool isPrime(int num){
    bool ret=false;
    if(num<=1||(num>2&&0==(num%2))){
        return ret;
    }
    if(2==num||3==num||5==num||7==num){
        ret=true;
        return ret;
    }
    if(0==(num%3)||0==(num%5)||0==(num%7)){
        return ret;
    }
    int limit=sqrt(num);
    ret=true;
    for(int i=11;i<=limit;i+=2){
        if(0==(num%i)){
            ret=false;
            break;
        }
    }
    return ret;
}
class Solution{
public:
    int maxPair(const std::vector<int>&data){
        int sz=data.size();
        std::vector<int> odds,evens;
        int res=0;
        for(int i=0;i<sz;i++){
            if(0==(data.at(i)%2)){
                evens.push_back(data.at(i));
            }else{
                odds.push_back(data.at(i));
            }
        }
        int m=evens.size(),n=odds.size();
        if(0==m||0==n){
            return res;
        }
        uint8_t used[m];
        std::vector<int> even_matchs;
        even_matchs.resize(m,0);
        for(int i=0;i<n;i++){
            memset(used,0,m*sizeof(uint8_t));
            if(find(odds.at(i),evens,even_matchs,used)){
                res++;
            }
        }
        return res;
    }
private:
    bool find(int odd,std::vector<int>&evens,
              std::vector<int>&even_matchs,uint8_t *used){
        for(int i=0;i<evens.size();i++){
            if((0==used[i])&&isPrime(odd+evens.at(i))){
                used[i]=1;
                if(0==even_matchs[i]||
                   find(even_matchs[i],evens,even_matchs,used)){
                    even_matchs[i]=odd;
                    return true;
                }
            }
        }
        return false;
    }
};
int main()
{
    std::vector<int> data;
    //{20923,22855 ,2817 ,1447 ,29277, 19736 ,20227 ,22422, 24712 ,27054, 27050, 18272, 5477, 27174,
     //13880, 15730 ,7982, 11464 ,27483, 19563, 5998, 16163};
    int n;
    std::cin>>n;
    for(int i=0;i<n;i++){
        int num;
        std::cin>>num;
        data.push_back(num);
    }
    Solution so;
    int ret=so.maxPair(data);
    std::cout<<ret<<std::endl;
    return 0;
}

Reference:
[1]二分图最大匹配（匈牙利算法）：素数伴侣https://www.cnblogs.com/xiehuazhen/p/12574797.html