题解 | #素数伴侣#

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#define MAX_COUNT 100

int oddCount = 0;
int evenCount = 0;

bool isprime(int figure);
void buildNetwork(int odds[], int evens[]);

int M[MAX_COUNT];
bool used[MAX_COUNT];
int network[MAX_COUNT][MAX_COUNT];
int odds[MAX_COUNT]; //奇数
int evens[MAX_COUNT]; //偶数

int findp(int j) {
    for (int i = 0; i < oddCount; i++) {
        if (network[i][j] == 1 && (used[i] == 0)) {
            used[i] = 1;
            if (M[i] == -1 || findp(M[i])) {
                M[i] = j;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int i, n, figure;
    scanf("%d", &n);

    memset(odds, -1, sizeof(odds));
    memset(evens, -1, sizeof(evens));
    for (i = 0; i < n; i++) {
        scanf("%d", &figure);
        if (figure % 2 == 0) {
            evens[evenCount++] = figure;
        } else {
            odds[oddCount++] = figure;
        }
    }
    buildNetwork(odds, evens);

    memset(M, -1, sizeof(M));
    int sum = 0;
    for (i = 0; i < evenCount; i++) {
        memset(used, 0, sizeof(used));
        sum = sum + findp(i);
    }

    printf("%d", sum);

    return 0;
}

bool isprime(int figure) {
    int i;
    for (i = 2; i * i <= figure; i++) {
        if (figure % i == 0) {
            return false;
        }
    }

    return true;
}

void buildNetwork(int odds[], int evens[]) {
    int i, j;
    int figure;
    for (i = 0; i < oddCount; i++)
        for (j = 0; j < evenCount; j++) {
            figure = odds[i] + evens[j];
            if (isprime(figure)) {
                network[i][j] = 1;
            }
        }
}