题目的主要信息：

• 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”
• 已知有$NN$个数，$NN$为偶数，从中挑选若干对组成“素数伴侣”
• 求最多能组成的“素数伴侣”对数
• 数组的范围是2-30000

我们首先要明白大于2的偶数不可能是素数，而我们的给的数组元素都是大于等于2的，因此两个数相加必定大于2，因此我们要求的配对必须一奇一偶配对才有可能构成“素数伴侣”。

方法一：暴力匈牙利算法

具体做法：

我们对于统计的数组分成奇数数组和偶数数组，如果其中有一个数组为空，则不可能构成“素数伴侣”。 然后就相当于是左边一些奇数元素的点，要连到右边偶数元素上面，这就是二分图连线最多的问题，我们可以用匈牙利算法。

首先我们遍历左边奇数数组，对每一个元素都查找能否在偶数数组中找到配对的数，查找时我们遍历偶数数组，如果该偶数能和这个奇数匹配，且在这一轮这个偶数没被用过，我们再检查这个match数组（表示现阶段偶数匹配的对象），如果match数组中这个偶数没有匹配对象，或者递归查找这个匹配对象可以有其他的偶数匹配，那我们修改该匹配对象为这个奇数，代表能找到匹配。

判断一个数$nn$是否是素数，我们只需要找它有无因子即能否被整除即可。从2开始遍历到该数前一个数$n-1n-1$，查看每个数能否整除$nn$，如果可以整除即余数为0，返回false，如果检查完所有的数都没有因子，则它是质数，返回true。

其实我们不用遍历到$n-1n-1$，遍历到$\sqrt{n}\backslash sqrt\; n$即可，因为$\sqrt{n}\backslash sqrt\; n$后面如果有因子，必定是乘上另一个小于$\sqrt{n}\backslash sqrt\; n$的数字，那我们前面就已经验证过了，因此以$\sqrt{n}\backslash sqrt\; n$为遍历终点就可以了。

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

bool isprime(int num){ //判断一个数是否是素数
    for(int i = 2; i * i <= num; i++){ //遍历到根号num
        if(num % i == 0) //检查有无余数
            return false;
    }
    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;
}

复杂度分析：

• 时间复杂度：$O(n{m}^2\sqrt{k})O(nm^2\; \backslash sqrt\; k)$，其中$nn$为奇数数组的长度，$mm$为偶数数组的长度，$k=ma{x}_{\mathrm{奇}\mathrm{数}}+ma{x}_{\mathrm{偶}\mathrm{数}}k=max\_\{奇数\}+max\_\{偶数\}$，我们外循环遍历奇数数组，内循环遍历偶数数组，但是内循环还有递归，因此最坏为$O(m^2)O(m^2)$，内循环每次还会判断相加是否是素数，判断一次不超过$O(\sqrt{k})O(\backslash sqrt\; k)$
• 空间复杂度：$O(max(n,m))O(max(n,m))$，递归栈及辅助数组空间不超过这个数值

方法二：哈希表优化匈牙利算法

具体做法：

我们可以用一个二维数组记录任意两个数之间能否可以组成“素数伴侣”，这样在方法一的find数组中，我们就不用每次都判断一次相加是否是素数了，直接查询二维数组即可，因为二维数组起到了哈希表的作用，因此这个方法叫做哈希表优化。

因为奇数数组与偶数数组元素都是不确定的，因此方法二我们不像方法一一样传入数据，而是用下标代替数组元素，反正根据下标就能查出这两个数组能否加成素数。

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

bool isprime(int num){ //判断一个数是否是素数
    for(int i = 2; i * i <= num; i++){ //遍历到根号num
        if(num % i == 0) //检查有无余数
            return false;
    }
    return true;
}

bool find(int index, vector<bool>& used, vector<int>& match, vector<vector<bool>>& map){
    for(int i = 0; i < used.size(); i++){ //遍历每个偶数与奇数比较
        if(map[i][index] && !used[i]){ //直接查询能否构成
            used[i] = true;
            if(match[i] == -1 || find(match[i], used, match, map)){ //如果第i个偶数还未配对，或者跟它配对的奇数还有别的选择
                match[i] = index; //则配对该数
                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<vector<bool>> map(evens.size(), vector<bool>(odds.size(), false));
        for(int i = 0; i < evens.size(); i++){ //构建所有能能够相连的奇数偶数的边
            for(int j = 0; j < odds.size(); j++){
                if(isprime(evens[i] + odds[j]))
                    map[i][j] = true;
            }
        }
        vector<int> match(evens.size(), -1); //统计每个偶数的配对是哪个奇数
        for(int i = 0; i < odds.size(); i++){ //遍历每个奇数
            vector<bool> used(evens.size(), false); //每一轮偶数都没用过
            if(find(i, used, match, map)) //能否找到配对的偶数，且要最优，不传数，传下标
                count++;
        }
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n{m}^2+nm\sqrt{k})O(nm^2\; +\; nm\backslash sqrt\; k)$，其中$nn$为奇数数组的长度，$mm$为偶数数组的长度，$k=ma{x}_{\mathrm{奇}\mathrm{数}}+ma{x}_{\mathrm{偶}\mathrm{数}}k=max\_\{奇数\}+max\_\{偶数\}$，我们外循环遍历奇数数组，内循环遍历偶数数组，但是内循环还有递归，因此最坏为$O(m^2)O(m^2)$，此外我们遍历二维数组每次还会判断相加是否是素数，判断一次不超过$O(\sqrt{k})O(\backslash sqrt\; k)$
• 空间复杂度：$O(mn)O(mn)$，最大辅助空间为二维数组的大小