题解 | #素数伴侣#

import math

# 1、分奇偶
def group_oe(nums_list):
    odds, evens = [], []
    for num in nums_list:
        if num % 2 == 0:
            evens.append(num)
        else:
            odds.append(num)
    return odds, evens


# 2、判断是否都为素数
def is_prime(num):  # 由题可知列表里均为自然数，所以 o+e > 2
    for i in range(3, int(math.sqrt(num)) + 3, 2):
        if num % i == 0:
            return False
    return True


# 3、记录 e+o 为素数时对应的索引
def matrix_oe(odds, evens):
    # 初始化二维矩阵,外层面循环为偶数，内层循环为奇数，找每一个偶数对应的奇数
    matrix = [[0 for _ in range(len(odds))] for _ in range(len(evens))]
    for ie in range(len(evens)):
        for io in range(len(odds)):
            if is_prime(evens[ie] + odds[io]):  # 偶数和奇数和为素数，则记为 1
                matrix[ie][io] = 1
    return matrix


# 寻找每一个偶数所对应的奇数
def find_eo(ie, odds, matrix, match_o, used_o):
    for io in range(len(odds)):
        # 从matrix矩阵中找到1，即奇+偶=素数
        # 同时used_o中找到0，即查询奇数是否已经匹配过偶数，没匹配过则更新为1
        if matrix[ie][io] == 1 and used_o[io] == 0:
            used_o[io] = 1
            # 然后查询match_o中的记录的可以匹配相应偶数的 奇数索引是否更新，未更新则更新，否则查看该位置之前对保存的偶数的是否能找到新的匹配的奇数
            if match_o[io] == -1 or find_eo(match_o[io], odds, matrix, match_o, used_o):
                match_o[io] = ie
                return True
    return False


# 素数伴侣
while True:
    try:
        # 接受输入数据
        n = int(input())  # 正整数n
        nums_list = list(map(int, input().split()))  # 组成素数的数组，以空格切分
        # 判断两数之和是否为素数，只需判断 奇+偶（因为两奇/偶数之和均为合数）
        # 1、分奇偶
        odds, evens = group_oe(nums_list)
        # 2、判断 奇+偶 是否都为素数
        # 3、奇+偶 为素数时，记录为1，二维矩阵的行和列分别对应odds和evens的索引。
        matrix = matrix_oe(odds, evens)
        # 4、利用匈牙利算法寻找最优解
        # 创建一个数组记录 与当前偶数可匹配的奇数在odds内的索引,初始化为 -1，不初始化为0是因为索引第一个就是0，防止冲突
        match_o = [-1 for _ in range(len(odds))]
        # 初始化变量，匹配成功一对（奇+偶），加 1
        count_oe = 0
        for ie in range(len(evens)):
            # 循环内初始化一个数组。记录与当前奇数有对应匹配的偶数，匹配成功记录为1
            used_o = [0 for _ in range(len(odds))]
            # 开始将每一个偶数与所有奇数相匹配
            # 需要输入偶数的索引ie, 奇数数组odds，匹配矩阵matrix,匹配偶数的奇数索引match_o,已经成功匹配到偶数的奇数数组used_o
            if find_eo(ie, odds, matrix, match_o, used_o):
                count_oe += 1
        print(count_oe)
    except:
        break