题解 | #素数伴侣#

1. 两数相加要是素数，必然一奇一偶，因此将数组分为奇数组和偶数组
2. 将奇数组和偶数组遍历，标记出和为素数的组合
3. 套用匈牙利算法找到所有的素数伴侣

代码如下：

//两数相加要为素数，则这两个数必然一个奇数一个为偶数
//将输入的数据分为奇数和偶数两部分
#include <math.h>
#define MAX_COUNT 100
int even[MAX_COUNT];   			 //存储偶数
int odd[MAX_COUNT];      		 //存储奇数
int line[MAX_COUNT][MAX_COUNT];  //标记以此下标(x,y)的两个数之和是素数
int used[MAX_COUNT];			 //标记此下标对应的奇数值是否被使用
int evenCount = 0;      		 //偶数计数
int oddCount = 0;				 //奇数计数
/* 判断是不是素数 */
int IsPrime(int num)
{
    for (int i = 2;i <= sqrt(num);i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

/* 遍历标记出符合两数之和为素数的组合 */
void Line()
{
    for (int i = 0;i < evenCount;i++) {
        for (int j = 0;j < oddCount;j++) {
            if (IsPrime(even[i] + odd[j]) == 1) {
                line[i][j] = 1;
            }
        }
    }
}

/* 将数组的元素分为偶数和奇数两部分，并做出标记 */
void IsEvenOrOdd(int num[], int n)
{
    for (int i = 0;i < n;i++) {
        if (num[i] % 2 == 0) {
            even[evenCount++] = num[i];
        } else {
            odd[oddCount++] = num[i];
        }
    }
    Line();
}
int oddEven[MAX_COUNT]; //存储第j个奇数匹配的偶数下标
/* 匈牙利算法，直到匹配的数，返回1，否则返回0 */
int FindPrimeMate(int n)
{
    for (int j = 0;j < oddCount;j++) {
        if ((line[n][j] == 1) && (used[j] == 0)) {
            used[j] = 1;
            if ((oddEven[j] == -1) || FindPrimeMate(oddEven[j])) {
                oddEven[j] = n;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int n = 0;
    int sum = 0;
    int num[MAX_COUNT] = {0};
    scanf("%d", &n);
    memset(oddEven, -1, MAX_COUNT*sizeof(int));
    for (int i = 0;i < n;i++) {
        scanf("%d", &num[i]);
    }
    IsEvenOrOdd(num, n);
    /* 遍历所有偶数，查找出与之匹配的奇数 */
    for (int i = 0;i < evenCount ;i++) {
    	/* 每一轮清除used标记 */
        memset(used, 0, MAX_COUNT);
        sum += FindPrimeMate(i);
    }
    printf("%d", sum);
    return 0;
}