题目的主要信息：

• 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”。
• 我们需要从一组数中，找出最多对的素数伴侣。

方法一：匈牙利算法

偶数+偶数=偶数，必不是素数，因此素数只能是奇数+偶数。我们把输入的这一组数分成奇数和偶数，就得到了二分图，在这两组之间用匈牙利算法作匹配。

1. 首先我们遍历一遍所有数字，建立他们之间所有可能的联系，便于后面的调整。接下来开始找最优连接方案。
2. 每次取奇数p，遍历偶数，判断是否能和奇数组成素数伴侣，如果偶数q没有和别人结成伴侣则建立p和q之间的关系；如果这个偶数q已经和别的奇数k结成伴侣，那么递归查找k的下一位能建立关系的偶数，如果找到了p和q建立关系，如果没有找到，则不改变偶数q和奇数k的关系。

匈牙利算法如下图例：

具体做法：

#include <iostream>
#include<vector>
using namespace std;
bool isprime(int i)//判断是否为素数
{
    for(int j=2;j*j<=i;j++)
    {
        if(i%j==0)
            return false;
    }
    return true;
}
bool find(const int & n,vector<vector<bool>> &map,vector<int>& match,vector<bool>&visit)
{
   for (int i = 0; i < match.size(); i++)
    {
        if (!visit[i] && map[i][n])//当前偶数未被访问过并且能和奇数n是素数伴侣
        {
            visit[i] = true;
            if (match[i] == -1 || find(match[i], map, match, visit))//当前偶数没有匹配或能给被抛弃的奇数找到新的偶数
            {
                match[i] = n;//建立偶数和奇数之间的连接
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n=0;
    while(cin>>n)
    {
        int k=0;//读取数据
        vector<int> even;
        vector<int> odd;
        int count=0;//匹配对数
        while(n--){//逐个输入按奇偶分类
            cin>>k;
            if(k%2==0){
                odd.push_back(k);
            }else{
                even.push_back(k);
            }
        }
        if(odd.empty()||even.empty()){//奇数或偶数为空则不会有素数伴侣
            cout<<count<<endl;
            continue;
        }
        vector<vector<bool>> map(even.size(),vector<bool>(odd.size(),false));
        for(int i=0;i<even.size();i++)//建立关系图，找出所有可能的连接
        {
            for(int j=0;j<odd.size();j++){
                if(isprime(even[i]+odd[j])){
                    map[i][j]=true;
                }
            }
        }
        vector<int> match(even.size(),-1);
        for (int i = 0; i < odd.size(); i++){
            vector<bool> visit(even.size(), false);//建立在当前奇数下对偶数的访问情况
            if (find(i, map, match, visit))
            {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(m{n}^2)O(mn^2)$，其中m为奇数个数，n为偶数个数，时间复杂度为$O(m)O(m)$for循环里嵌套着递归$O(n^2)O(n^2)$。
• 空间复杂度：$O(mn)O(mn)$，需要建立奇数和偶数之间连接表。

方法二：

方法二也是匈牙利算法，区别在于方法二去掉了了存储偶数和奇数之间关系的图，减少了空间，但是提高了时间复杂度，每次find函数递归遍历的时候都需要重新判断当前两个数是否为素数伴侣。

具体做法：

#include <iostream>
#include<vector>
using namespace std;
bool isprime(int i)//判断是否为素数
{
    for(int j=2;j*j<=i;j++)
    {
        if(i%j==0)
            return false;
    }
    return true;
}
bool find(const int & n,vector<int> &even,vector<int>& match,vector<bool>&visit)
{
   for (int i = 0; i < even.size(); i++)
    {
        if (!visit[i] && isprime(even[i]+n))//当前偶数未被访问过并且能和奇数n是素数伴侣
        {
            visit[i] = true;
            if (match[i] == -1 || find(match[i], even, match, visit))//当前偶数没有匹配或能给被抛弃的奇数找到新的偶数
            {
                match[i] = n;//建立偶数和奇数之间的连接
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n=0;
    while(cin>>n)
    {
        int k=0;//读取数据
        vector<int> even;
        vector<int> odd;
        int count=0;//匹配对数
        while(n--){//逐个输入按奇偶分类
            cin>>k;
            if(k%2==0){
                odd.push_back(k);
            }else{
                even.push_back(k);
            }
        }
        if(odd.empty()||even.empty()){//奇数或偶数为空则不会有素数伴侣
            cout<<count<<endl;
            continue;
        }
        vector<int> match(even.size(),-1);
        for (int i = 0; i < odd.size(); i++){
            vector<bool> visit(even.size(), false);//建立在当前奇数下对偶数的访问情况
            if (find(odd[i], even, match, visit))
            {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(m(kn{)}^2)O(m(kn)^2)$，k为判断是否为素数的时间复杂度。
• 空间复杂度：$O(1)O(1)$。