题意：



方法一：
匈牙利算法求最大匹配

思路：
            题目的意思是叫求最大匹配。
            然后，构造二分图，因为题目中输入的数据大小满足，所以最小的两数之和为4。
            因此素数的最小值为5，所以素数要满足奇数的条件。
            因此，可以将输入数据分为奇数和偶数两部分，构造二分图；
            如果奇数部分和偶数部分各取一个数相加的和是素数，则说明两个数之间存在一条边。
            最后，利用匈牙利算法即可解得最大匹配数量。

           
#include <bits/stdc++.h>

using namespace std;
int a[105];
int b[105];//奇数
int c[105];//偶数
int vis[30005];
int match[30005];
int n1,n2;

int isPrime(int x){//判断是否是素数
    if(x<=1)
        return 0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)
            return 0;
    }
    return 1;
}

int Find(int x){//匈牙利算法
    for(int i=0;i<n2;i++){
        if(isPrime(x+c[i])){//遍历相连的边
            int y=c[i];
            if(vis[y]==0){//如果未被访问，则访问
                vis[y]=1;
                if(match[y]==0||Find(match[y])){//如果未被匹配或已被匹配但匹配的对方可以换一个对象，则成功
                    match[y]=x;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(){
    int n;
    while(cin >> n){
        memset(match,0,sizeof(match));
        int res=0;
        n1=0;
        n2=0;
        for(int i=0;i<n;i++){
            cin >> a[i];
            if(a[i]%2)//构造二分图
                b[n1++]=a[i];//奇数数组
            else
                c[n2++]=a[i];//偶数数组
        }
        for(int i=0;i<n1;i++){//匈牙利算法寻找二分图的最大匹配
            memset(vis,0,sizeof(vis));
            if(Find(b[i]))//如果匹配成功，则结果加一
                res++;
        }
        cout << res << endl;
    }
    
    return 0;
}


时间复杂度：
空间复杂度：O(n+m)，n是数组大小，m是数字的最大值，存储数组、vis[\ ]、match[\ ],递归栈的复杂度是O(n).

方法二：
素数优化+set

思路：
        首先，打素数表，可以用欧拉线性筛获得素数表。
        后面，将素数表存储在无序set中，之后就可以直接O(1)时间复杂度判断是否是素数。
#include <bits/stdc++.h>

using namespace std;
int a[105];
int prime[60005];//存储素数
int isPrime[60005];//判断是否是素数
int cnt=0;
unordered_set<int> st;
int b[105];//奇数
int c[105];//偶数
int vis[30005];
int match[30005];
int n1,n2;

int Find(int x){//匈牙利算法
    for(int i=0;i<n2;i++){
        if(st.count(x+c[i])){//遍历相连的边
            int y=c[i];
            if(vis[y]==0){//如果未被访问，则访问
                vis[y]=1;
                if(match[y]==0||Find(match[y])){//如果未被匹配或已被匹配但匹配的对方可以换一个对象，则成功
                    match[y]=x;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(){
    for(int i=2;i<=60000;i++){//线性筛素数  打素数表
        if(isPrime[i]==0)//默认0表示素数
            prime[cnt++]=i;//添加素数
        for(int j=0;j<cnt&&i<=60000/prime[j];j++){
            isPrime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
    for(int i=0;i<cnt;i++)
        st.insert(prime[i]);
    int n;
    while(cin >> n){
        memset(match,0,sizeof(match));
        int res=0;
        n1=0;
        n2=0;
        for(int i=0;i<n;i++){
            cin >> a[i];
            if(a[i]%2)//构造二分图
                b[n1++]=a[i];//奇数数组
            else
                c[n2++]=a[i];//偶数数组
        }
        for(int i=0;i<n1;i++){//匈牙利算法寻找二分图的最大匹配
            memset(vis,0,sizeof(vis));
            if(Find(b[i]))//如果匹配成功，则结果加一
                res++;
        }
        cout << res << endl;
    }
    
    return 0;
}

时间复杂度：
空间复杂度：