素数伴侣

from math import sqrt


def is_prime(num: int) -> bool:
    if num < 2:
        return False
    elif num == 2:
        return True
    else:
        for i in range(2, int(sqrt(num) + 1)):
            if num % i == 0:
                return False
        return True


def mate(
    odd: int,
    final_selection: list[int],
    temporary_selection: list[int],
    evens: list[int],
):
    for i in range(len(evens)):
        if is_prime(odd + evens[i]) and temporary_selection[i] == -1:
            temporary_selection[i] = 1  # 1只表示evens[i]暂时被选了
            if final_selection[i] == -1&nbs***bsp;mate(
                final_selection[i], final_selection, temporary_selection, evens
            ):
                final_selection[i] = odd
                return True
    return False


n = int(input())
numbers = [int(i) for i in input().strip().split()]

# 奇数+奇数=偶数，偶数+偶数=偶数，都不能成为素数。只能奇数+偶数的组合才有可能
# 第一步：分奇偶
odds, evens = [], []
for num in numbers:
    if num % 2 == 0:
        evens.append(num)
    else:
        odds.append(num)
# 第二步：二分图最佳匹配
count = 0
final_selection = [-1] * len(evens)
for odd in odds:
    temporary_selection = [-1] * len(evens)
    if mate(odd, final_selection, temporary_selection, evens):
        count += 1
print(count)


# 考察点：匈牙利算法（二分图最佳匹配算法）

def issu(x):
    tem = 2
    while tem ** 2 < x+1:
        if x % tem == 0:
            return False
        tem += 1
    return True

def find(a,list1,list2,list3):
    for i in range(len(list3)):
        if issu(a + list3[i]) and list1[i] == 0:
            list1[i] = 1
            if list2[i] == 0&nbs***bsp;find(list2[i],list1,list2,list3):
                #上边，如果list2【i】不为零，则将该位置上的奇数，和本次剩余的偶数进行匹配，
                #如果找的到，占用此数的位置，否则返回失败
                list2[i] = a
                return True
    return False
while True:
    try:
        n = int(input())
        l = list(map(int,input().strip().split()))
        j = [] #奇数队
        o = [] # 偶数队
        for i in range(n):
            if l[i] % 2 == 0:
                o.append(l[i])
            else:
                j.append(l[i])
        count = 0
        match = [0] * len(o)
        for i in range(len(j)):
            used = [0] * len(o)
            if find(j[i],used,match,o):
                count += 1#每次配对成功一次进行记数一次
        print(count)
    except:
        break

了解匈牙利算法的思想以后终于能看懂大佬们的题解了。手打一遍并记下实现过程。

匈牙利算法思想：https://blog.csdn.net/sunny_hun/article/details/80627351

实现要点：

1.奇偶分组：
用偶数组当做待选列表，每次拿一个奇数，到偶数列表中选对象。

2.两个工具：
-->占用表ocu 随着每个奇数重新初始化，在每个奇数配对的单轮循环内标记已被占用的偶数（0代表可用，1代表占用）。

-->配对表mtch 只初始化一次，标注j下标的偶数配给了哪个奇数。
配对表随着奇数检查即时更新。

3.find函数
角色：承载检查目标奇有无配对状态，并在检查过程中更新配对表
传入：目标奇，占用表，配对表，偶数列表
返回：能(True)否(False)配对
配对规则：如果配对表记录当前偶无对象，或者有对象（不是目标奇，简称原配奇）但是有其他偶数能挪给原配奇，就让目标奇配当前偶

以上几个要点清晰了以后，整个方案就清楚了。

def ispair(x:int, y:int)->bool:
    n,m = int((x+y)**0.5)+1, x+y
    for i in range(2,n):
        if m%i==0: return False
    return True
def find(odd:int, ocu:list, mtch:list, even:list)->bool:
    for j in range(len(even)):
        if ispair(odd,even[j]) and ocu[j]==0:  #如果当前偶跟目标奇能配对，而且当前偶还没被登记占用，就把当前偶占住
            ocu[j]=1
            if mtch[j]==0 or find(mtch[j],ocu,mtch,even):  #如果配对表记录当前偶没对象，或者有对象（不是目标奇，简称原配奇）但是有其他偶数能挪给原配奇，就让目标奇配当前偶
                mtch[j]=odd
                return True
    return False
while True:
    try:
        n,arr,odd,even = int(input()),list(map(int,input().split())),[],[]
        for i in range(n):
            if i%2==0: even.append(i)
            else: odd.append(i)
        mtch = [0]*len(even)
        result = 0
        for i in range(len(odd)):  #遍历odd列表
            ocu = [0]*len(even)  #对于每个奇数，首先初始化现有的偶数占用方案，然后调用find函数看能不能找到配对偶数
            if find(odd[i],ocu,mtch,even):
                result += 1
        print(result)
    except:
        break

import itertools
while True:
    try:
        import itertools

        n = int(input())
        s = [int(i) for i in input().split()]


        def isprime(x):
            flag = True
            for i in range(2, x):
                if x % i == 0:
                    flag = False
                    break
            return flag


        def iscouple(x, y):
            return isprime(x + y)


        l1 = []
        l2 = []
        for i in s:
            if i % 2 != 0:
                l1.append(i)
            else:
                l2.append(i)

        if len(l1) < len(l2):
            tmp = l1
            l1 = l2
            l2 = tmp
        ls = []
        for i in l2:
            for j in l1:
                if iscouple(i, j):
                    ls.append([i, j])

        lc = []
        for x in itertools.permutations(l1, len(l2)):
            count = 0
            lt = []
            for i in range(len(l2)):
                lt.append([l2[i], x[i]])
            lr = [val for val in ls if val in lt]
            lc.append(len(lr))
            if len(lr) == len(l2):
                break

        print(max(lc))
    except:
        break
                    

            
        
                    
                
                
                
                
                
                

def su(a):
    tem = 2
    while tem**2 <= a:
        if a%tem == 0:
            return False
        tem += 1
    return True

def fmatrix(a,b):
    m = [[0 for _ in b] for _ in a]
    for ii, i in enumerate(a):
        for jj, j in enumerate(b):
            if su(i+j):
                m[ii][jj] = 1
    return m

def find(x):
    for i in range(len(odd)):
        if matrix[x][i] == 1 and used[i] == 0:
            used[i] = 1
            if match[i] == -1&nbs***bsp;find(match[i]) != 0:
                match[i] = x
                return True
    return False

while True:
    try:
        n = int(input())
        nums, odd, even = list(map(int,input().split())), [], []
        count = 0
        for i in nums:
            if i%2 == 0:
                even.append(i)
            else:
                odd.append(i)
        matrix = fmatrix(even,odd)
        match = [-1]*len(odd)
        for i in range(len(even)):
            used = [0]*len(odd)
            if find(i):
                count += 1
        print(count)
    except:
        break
看了了多个评论又自己在网上找了一些资料才搞懂了思路与匈牙利算法，自己写了一遍，用例全过