题解 | #素数伴侣#

import itertools
from typing import Iterable

PRIME_SET = {2}
def is_prime(n: int) -> bool:
    if n in PRIME_SET:
        return True
    if n <= 1:
        return False
    for x in range(2, n):
        if n % x == 0:
            return False
    PRIME_SET.add(n)
    return True

def try_match(match_dict, current_x, iterable_2,visited):
    i_x,x = current_x
    for i_y,y in enumerate(iterable_2):
        current_y = (i_y,y)

        if is_prime(y+x) and current_y not in visited:
            visited.add(current_y)
            # 如果Y没有配对，那么配对 | 如果有配对记录，那么尝试重新配对的old_x (match_dict[current_y])
            if current_y not in match_dict or try_match(match_dict,match_dict[current_y],iterable_2,visited):
                # 如果返回真则代表旧的找到了新配对
                match_dict[current_y] = current_x
                return True
    return False

def KM_algorithm(iterable_1,iterable_2):
    match_dict = {} # 保存 {(index_y,y):(index_x,x), ...}

    for i_x,x in enumerate(iterable_1):
        # 寻找可以和iterable2 中配对的数
        # 如果所有的iterable2 的数字都配对完成了, 那么该终止循环
        if len(match_dict) == len(iterable_2):
            break
        visited = set()
        try_match(match_dict, (i_x,x), iterable_2,visited)
        
    # print(match_dict)
    return len(match_dict)

l = int(input())
num_list = list(map(int , input().split()))

odd_list = list(filter(lambda x: x%2 ==1 ,num_list))
even_list = list(filter(lambda x: x%2 ==0 ,num_list))

# print(odd_list,even_list)
print(KM_algorithm(odd_list,even_list))

不够简洁的回答。匈牙利算法的核心是：

1. 从两个列表x,y 中任选一个数。这里从列表x中选择任意一个数a。
2. 创建一个集合v （来确保不要重复遍历 列表y里面的元素）和一个字典K，里面用来记录 y元素对应的x元素 类似于{y : x }
3. 然后尝试a和另外一个列表y里面寻找可以配对的对象
1. 如果 遍历到的y里面的元素b 和a 相加 为质数，且y不在集合v里面，那么就先把这个属于y的元素记录到集合v里，确保没有重复遍历
1. 判断b是不是在字典里面，或者 ( K[b] 遍历 （列表y 减去 已访问的元素 集合v）能不能找到新的配对对象）

遍历。。。。
如果b是质数，且没有遍历过：
	visited 添加 这个b
	if b not in K or try_match(K, K[b], visited):
	  #K 是保存{y元素:a元素} 这样关系的字典 
	  #K[b] 是当前这个关系里面对应的 a元素的值
		K[b] = a
		return True
return False

1. 如果二者任意返回真, 那么让字典K保存组合并且返回真
1. 全部遍历完都没有返回真，那么就找不到关系，返回False