题解 | #素数伴侣#

#include <stdio.h>
#include <math.h>
// 解本题的关键就是最大匹配算法（匈牙利算法）
// 把数组分2类，奇和偶，再依次匹配，没当找到一个增广路径，匹配数++
//  存放偶数数组  存放奇数数组   存放第i个偶数与第j个奇数是否能配对
int oddNum[100], eddNum[100], findPos[100][100];
int visit[100];
int oddlen = 0; //偶数个数
int eddlen = 0; // 奇数个数
int sum = 0; // 匹配个数
//  标记第i个偶数是否以及与第od[i]个奇数配对
int od[100];
//  标记第j个偶数是否以及与第od[j]个奇数配对
int ed[100]; 


// 判断是否为素数
int FindComNum(int sum)
{
    for (int i = 2; i < sqrt(sum) + 1; i++)
    {
        if (sum % i == 0)
        {
            return 0;//不是素数
        }
    }
    return 1; // 是素数
}

//找到偶数数组
int FindoddNum(int src[], int n)
{
    for (int i = 0; i < n; i++) {
        if (src[i] % 2 == 0)
        {
            oddNum[oddlen++] = src[i];
        }
    }
    return 0;
}

// 找到奇数数组
int FindeddNum(int src[], int n)
{
    for (int i = 0; i < n; i++) {
        if (src[i] % 2 != 0)
        {
            eddNum[eddlen++] = src[i];
        }
    }
    return 0;
}

// 配对
int dfs(int u)
{
    for (int i = 0; i < 100; i++)
    {
        if (findPos[u][i] != 0 && !visit[i])  // 当能够配对，并且奇数没有访问
        {
            visit[i] = 1; //标记 有配对的可能
            // 再判断是否有伴侣或者与其配对的偶数能够换一位奇数
            if (ed[i] == -1 || dfs(ed[i]))
            {
                ed[i] = u; //第 i 位奇数与第u位偶数配对
                od[u] = i; // 第 u 位偶数与第i位奇数配对
                return 1;
            }

        }
    }
    return 0;//没有找到
}

int main() {
    int n;
    scanf("%d", &n);
    int modelNum[100];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &modelNum[i]);
    }
  
  	// 初始化
    for (int i = 0; i < oddlen; i++)
    {
        for (int j = 0; j < eddlen; j++)
        {
            findPos[i][j] = 0;
        }
	}
  
    for (int i = 0; i < oddlen; i++)
    {
        od[i] = -1;
    }   
    for (int i = 0; i < eddlen; i++)
    {
        ed[i] = -1;
        //printf("%d ", ed[i]);
    }
    // 分数组
    FindeddNum(modelNum, n);
    FindoddNum(modelNum, n);
  
    // 初始化findPos
    for (int i = 0; i < oddlen; i++)
    {
        for (int j = 0; j < eddlen; j++)
        {
            if (FindComNum(oddNum[i] + eddNum[j]))
            {
                findPos[i][j] = 1;
                //printf("%d ",findPos[i][j]);
            }
        }
    }

    for (int i = 0; i < oddlen; i++)
    {
        if (od[i] == -1)
        {
            for (int j = 0; j < eddlen; j++)
            {
                visit[j] = 0;
            }
            sum = sum + dfs(i); // 找到新的一个匹配
        }
    }
    printf("%d\n", sum);
    return 0;
}