题解 | #素数伴侣# 匈牙利算法

二分图的其中一个简便解法，评论区的第一个详细解说暂时还没看懂，这里就先记录下抄作业后的理解
偶数列表odds
奇数列表evens
素数判断函数get_primenum逻辑是判断从2到根号s之间的整数能否被s整除，能的话就不是素数
首先将数字按奇偶数分组，最外层的for循环我用的是偶数，所以需要构造一个匹配奇数的方法find_even。这个方法在内部做了递归，在匹配到的奇数已经有配对值时使用。
此方法逻辑如下：

遍历奇数列表，判断遍历到的数字与入参偶数相加是否时素数
如果是素数，其入参的pre_select[i]是否是0（即未访问过）？
若是，赋值pre_select[i]=1标记访问，且判断其入参的final_select[i]是否为0
（若是，将赋值后的pre_select与其他参数传入find_even，如此递归，判断返回值 返回值与前述判断final_select[i]是否为0的逻辑为或的关系
若该或逻辑最终为真，则赋值其位值为入参偶数final_select[i]=odd，并返回True）
否则进入下一个奇数判断
若最终找不到匹配的奇数，便返回False，

在外层for循环时，每次初始化一个pre_select空数组，pre_select=[0]*len(evens)，传到前述的匹配奇数方法里，判断返回值是否是True，是则计数count0+=1
最后打印的count即是所求值

import sys,math

# 判断素数
def get_primenum(s):
    if s<4:return True
    for i in range(2,int(s**0.5)+1):
        if s%i==0:return False
    return True

# 寻找奇数
def find_even(evens,pre_select,final_select,odd):
    for i,even in enumerate(evens):
        # 如果遍历到的偶数与入参的奇数相加是素数 且在pre_select中对应数为0
        if get_primenum(even+odd) and pre_select[i]==0:
            # 赋值其为1
            pre_select[i]=1
            # 判断第i位奇数是否被匹配或其匹配到的偶数是否有其他选择
            if final_select[i]==0 or find_even(evens, pre_select, final_select, final_select[i]):
                final_select[i]=odd
                return True
    return False

# 根据现在牛客ACM模式要求取数据用的
N=0
list0=[]
for line in sys.stdin:
    a = line.split()
    if len(a)==1:
        N=a[0]
    else:
        list0=a

# 正式开始计算
count0=0
# 偶数列表，奇数列表
evens,odds=[],[]
for list1 in list0:
    list1=int(list1)
    if list1%2==0:
        evens.append(list1)
    else:
        odds.append(list1)
# 最后被选择的列表
final_select = [0]*len(evens)
# 遍历偶数
for odd in odds:
    # 初始化一个已被匹配的记录数组
    pre_select=[0]*len(evens)
    if find_even(evens, pre_select, final_select, odd):
        count0+=1
print(count0)