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

import math

def sushu(sushu1, sushu2):
    o = sushu1 + sushu2
    for i in range(2, int(math.sqrt(o)) + 1):
        if o % i == 0:
            return False
    return True

geshu = int(input())
ngezhengshu = input().split()
jishu = []
oushu = []
for zhengshu in ngezhengshu:
    if int(zhengshu) > 0 and int(zhengshu) % 2 == 1:
        jishu.append(int(zhengshu))
    elif int(zhengshu) > 0 and int(zhengshu) % 2 == 0:
        oushu.append(int(zhengshu))
jilu = [[]]
for jishu1 in jishu:
    jilu1 = []
    for oushu1 in range(len(oushu)):
        if sushu(jishu1, oushu[oushu1]):
            jilu1.append(oushu[oushu1])
    if len(jilu1) > 0:
        jilu.append(jilu1)
del jilu[0]
kshuzu = jilu
jieguo = []
op = []
while len(kshuzu) > 0:
    p = {}
    for pshuzu1 in kshuzu:
        for pkey in pshuzu1:
            if pkey not in p:
                p[pkey] = 1
            else:
                p[pkey] += 1
    yaosandecishu = min(p.values())
    yaosande = 0
    for key in p:
        if p[key] == yaosandecishu:
            yaosande = key
    kshuzu = sorted(kshuzu, key=len)
    for kshuzu1 in kshuzu:
        for k in kshuzu1:
            if k == yaosande and k in jieguo:
                kshuzu1.remove(yaosande)
            elif k == yaosande and k not in jieguo:
                jieguo.append(k)
                op = kshuzu1
    if op in kshuzu:
        kshuzu.remove(op)
    while [] in kshuzu:
        kshuzu.remove([])
print(len(jieguo))

因为不知道匈牙利算法，采取了另一种方法。

第一步，将输入的数分为奇数和偶数。

第二步，求出可以与奇数配对的偶数，按奇数的不同，分别存入若干个数组中。

此时，问题便转化为