题解 | #素数伴侣#

# 判断素数
def is_prime(n):
    m = int(n ** 0.5) + 2
    for i in range(3, m, 2):
        if n % i == 0:
            return False
    return True
def find_prime_pairs(n, nums):
    
    #分为奇数和偶数两个列表，素数比为奇数和偶数的和
    odds = [num for num in nums if num % 2 == 1]
    evens = [num for num in nums if num % 2 == 0]
    
    # 构建图的邻接表
    adj = {odd: [] for odd in odds}
    for odd in odds:
        for even in evens:
            if is_prime(odd + even):
                adj[odd].append(even)
    
    # 匈牙利算法寻找最大匹配
    def bpm(u, match, visited):
        for v in adj[u]: #v为可以与当前奇数组成素数的偶数
            if not visited[v]:
                visited[v] = True #如果当前偶数已经配对但还与当前奇数匹配，visited[v]用来控制先前配对的奇数看其他节点
                if v not in match or bpm(match[v], match, visited): #如果当前偶数没有配对则直接配对成功;如果当前偶数已经被分配，再找之前与之匹配的奇数还有没有其他偶数可以配对的，如果有就更改一下配对，当前奇数和之前的奇数都会匹配成功,此时visited会产生作用,相当于回溯重新分配
                    match[v] = u
                    return True
        return False
    match = {} #记录匹配关系
    result = 0
    for odd in odds:#为每个奇数分配偶数，如果成功+1
        visited = {even: False for even in evens}
        if bpm(odd, match, visited):
            result += 1
    return result
n = int(input())
val = list(map(int, input().split(" ")))
result = find_prime_pairs(n, val)
print(result)