题解 | #素数伴侣# 【二分图匈牙利算法】

#这道题的难点在于找出不同的情况，以下代码是只判断一种情况下的素数伴侣的情况
#经过研究，这道题的解法是二分图匈牙利算法
#因为一个素数一定由一个偶数和一个奇数组成（除了2）
#所以该问题修改为：已知偶数数列a和奇数数列b，求符合条件的配对最多有多少对

def isPrime(x):
    if (x == 2) or (x == 3):
        return True
    if (x % 6 != 1) and (x % 6 != 5):
        return False
    for i in range(5, int(x ** 0.5) + 1, 6):
        if (x % i == 0) or (x % (i + 2) == 0):
            return False
    return True


def isPartner(a,b):
    if isPrime(int(a)+int(b)):
        return True
    else:
        return False

#让列表中的数字两两组合，组合后就剔除，

n = int(input())
num_list = input().split(' ')

odd_list = []
even_list = []
for num in num_list:
    if int(num)%2 == 0:
        even_list.append(num)
    else:
        odd_list.append(num)

count = 0 #素数伴侣数量

# 匈牙利算法部分

# 这是匈牙利算法的核心部分，用于在二分图中寻找增广路径并进行匹配
# u: 当前偶数节点的索引
# adj_list: 邻接表，表示偶数节点与可以匹配的奇数节点的关系
# match: 匹配数组，表示奇数节点已匹配的偶数节点索引
# visited: 记录奇数节点是否被访问过的数组
def find_partner(u, adj_list, match, visited):
    for v in adj_list[u]:  # 遍历与当前偶数节点相连的所有奇数节点
        if not visited[v]:  # 如果奇数节点没有被访问过
            visited[v] = True  # 标记奇数节点为已访问
            if match[v] == -1 or find_partner(match[v], adj_list, match, visited):
                # 如果奇数节点未匹配，或者可以找到增广路径
                match[v] = u  # 进行匹配
                return True
    return False

adj_list = {}  # 邻接表，存储偶数节点与奇数节点的关系
for i in range(len(even_list)):
    adj_list[i] = []  # 初始化邻接表
    for j in range(len(odd_list)):
        if isPartner(even_list[i], odd_list[j]):  # 如果偶数节点与奇数节点可以匹配
            adj_list[i].append(j)  # 将奇数节点加入邻接表中

match = [-1] * len(odd_list)  # 初始化匹配数组，表示奇数节点尚未匹配
for u in range(len(even_list)):  # 遍历所有偶数节点
    visited = [False] * len(odd_list)  # 初始化访问数组
    if find_partner(u, adj_list, match, visited):  # 尝试在当前偶数节点上找增广路径
        count += 1  # 如果找到了增广路径，匹配数增加

print(count)  # 输出最大匹配数，即最多的素数伴侣组合数













'''以下代码是只能考虑一种情况的一开始写的代码

count = 0 #素数伴侣数量

list_done = [] #存储已经被记录的index
for i in range(len(num_list)):
    for j in range(len(num_list)):
        if i in list_done or j in list_done:
            pass
        elif i == j:
            pass
        elif isPartner(num_list[i],num_list[j]):
            list_done.append(i)
            list_done.append(j)
            count += 1
        else:
            pass
print(count)
'''