题解 | #素数伴侣#

本题的思路是：如果是素数，一定是奇数和偶数结合（奇数）才有可能是素数，所以将需要配对的数分为两组，一组是奇数，一组是偶数，通过匈牙利算法求得最大的配对数 配对的思路是，可以把偶数和奇数当初来相亲的一些男女，首先一对男女相亲成功结婚了，然后另一个男生发现他和这个女生也合适，他就拆散这两个人，自己和这个女生结婚，让这个前夫哥再寻找自己的结婚对象，这样递归，直到能够再这些相亲的男女中找出最多对的夫妻

import math
def check(num): #判断是否是素数
    for i in range(2,int(math.sqrt(num)) + 2): #除去1和本身的数没有其他的因子称为素数，但其实检验到int(math.sqrt(num)) + 1即可（数学证明略），不然会超时
        if(num % i == 0):
            return False
    return True

def find(odd, visited, choose, evens): #配对的过程
    for j,even in enumerate(evens):  
        if check(odd+even) and not visited[j]: #如果即能配对，这两个数之前没有配过对（即使两个不能配对visit值为0，但是也不能过是否是素数这一关，所以visit就可以
        看为两个能配对的素数是否能配对）
            visited[j] = True #代表这两个数能配对
            if choose[j]==0 or find(choose[j],visited,choose,evens): #如果当前奇数没有和任何一个偶数现在已经配对，那么认为找到一组可以连接的，如果当前的奇数
            已经配对，那么就让那个与之配对的偶数断开连接，让他再次寻找能够配对的奇数
                choose[j] = odd #当前奇数已经和当前的偶数配对
                return True 
    return False 如果当前不能配对则返回False

while True:
    try:
        num = int(input())
        a = input()
        a = a.split()
        b = []
        count = 0
        for i in range(len(a)):
            a[i] = int(a[i])
        evens = []
        odds = []
        for i in a: #将输入的数分为奇数和偶数
            if(i % 2 == 0):
                odds.append(i)
            else:
                evens.append(i)
        choose = [0]*len(evens) #choose用来存放当前和这个奇数配对的那个偶数
        for odd in odds:
            visited = [False]*len(evens) #visit用来存放当前奇数和偶数是否已经配过对
            if find(odd,visited,choose,evens):
                count += 1
        print(count)
    except:
        break