题解 | #密码验证合格程序#

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX(a, b) ((a > b) ? (a) : (b))
static unsigned short g_int[100]; /* 输入的原始全部数据，并按先奇数，再偶数的顺序排列 */
static int g_num[2]; /* 1 表示输入数据的总数量，0表示奇数的总数量 */
static char g_status[100]; /* 偶数是否匹配过，且保持匹配过的奇数下标索引值，该数值初始化为 101 */
static bool g_curFlag[100]; /* 当前轮的是否匹配过的标记 */
static bool match(int odd)
{
    for (int j = g_num[0]; j < g_num[1]; j++) { /* 偶数范围 */
        if (g_curFlag[j] == true) continue;
        int k = 2, data = g_int[odd] + g_int[j];
        for (; k * k <= data;  k++) if (data % k == 0) break;
        if (k * k <= data) continue;

        g_curFlag[j] = true;
        if ((g_status[j] == 101) || match(g_status[j])) {
            g_status[j] = odd;
            return true;
        }
    }

    return false;
}

int main(int argc, char** argv)
{
    int acount = 0;
    scanf("%d", &g_num[1]);
    for (int i = 0; i < g_num[1]; i++) scanf("%hd", g_int + i);

    g_num[0] = g_num[1]; /* 假定所有数为奇数，遍历全表，如果有偶数，则移动到后面 */
    while ((g_num[0] > 0) && (g_int[g_num[0] - 1] % 2 == 0)) g_num[0]--;
    for (int i = 0; i < g_num[0]; i++) {
        if (g_int[i] % 2 != 0) continue;
        while ((g_num[0] - 1 > i) && (g_int[g_num[0] - 1] % 2 == 0)) g_num[0]--;
        if (g_num[0] - 1 > i) {
            g_int[i] ^= g_int[g_num[0] - 1] ^= g_int[i] ^= g_int[g_num[0] - 1]; g_num[0]--;
        }
        while ((g_num[0] - 1 > i) && (g_int[g_num[0] - 1] % 2 == 0)) g_num[0]--;
    }

    memset(g_status, 101, sizeof(g_status));
    for (int i = 0; i < g_num[0]; i++) { /* 奇数范围 */
        memset(g_curFlag, 0, sizeof(g_curFlag));
        if (match(i)) acount++;
    }
    printf("%d\n", acount);
    return 0;
}