#素数伴侣#呆喵挠琴->匈牙利算法终极举例注释版本

#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;
}
// vector<int> match(even.size(),-1);
// vector<bool> visit(even.size(), false);
// n是需要匹配的奇数
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-odd i-even
        {
                visit[i]=true;
                if(match[i]==-1||find(match[i], map, match,visit))// 没有匹配过||或者是匹配过的奇数 重新进行匹配
                {
                    match[i]=n;
                    return true;
                }
        }
    }
    return false;
}
/*
1.代码流程- 先按照输入分为 odd 和 even          素数情侣只能在奇数+偶数里面  但并不是所有的奇数+偶数都是素数
2.遍历每个奇数和每个偶数的组合形成 map子图
3.find函数是最为关键的函数  输入：所求的奇数/ map子图/ match 记录该偶数所匹配的奇数（唯一）
/vist判断该偶数是否有访问过（每个新的奇数都刷新vist）  vist数组的作用 防止被重复访问
举例说明   A可以匹配 a 和b  B只可以匹配a  
运行过程:    if(!visit[i]&&map[i][n]) -> a没有被访问过且 A和a可以匹配
             visit[i]=true;           -> 记录a被访问过了
            if(match[i]==-1||find(match[i], map, match,visit)) ->此时a没有被匹配过  前者成立
             match[i]=n;//记录 a所匹配的为A
此时A-a形成关系

进行下个循环 寻找B的匹配关系 此时vist数组被刷新了
运行过程:    if(!visit[i]&&map[i][n]) -> a没有被访问过且B和a可以匹配
             visit[i]=true;           -> 记录a被访问过了 （保证递归的时候不会被重复访问）第一次访问
            if(match[i]==-1||find(match[i], map, match,visit)) -> a被匹配过了-前者不通过 //此时还在找B的
            // a被占用了已经   B想抢a 那要问A是否有空余的？ 如果有 A更换匹配关系 如果没有 A与a绑死 B找下一个匹配关系
             -> ||递归进入 匹配a的是A 进入A的递归函数      a已经被访问过了（第二次）  进入b   b与A可以匹配 
            更新匹配关系 A与b匹配 返回true 此时递归结束
            判断为真 
            B与a 更新匹配关系
            match[i]=n;//记录 a所匹配的为B
*/
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;

}
// 64 位输出请用 printf("%lld")