题解 | #素数伴侣#

from os import RTLD_DEEPBIND
import math
# 判断是否是素数
def ifprimary_num(n):
    for j in range(2,int(math.sqrt(n))+2):
        if n%j==0:
            return False
    return True

# 匈牙利算法（二分图）：素数必定是由一个偶数一个奇数相加得到的，可以把n个数分成偶数组和奇数组，偶数挨个与奇数相加，若为素数，则标记已用，下一个偶数和下一个奇数相加，。。。
def match(even,visit,p,odds):  # even int型，odds 列表
      
    for i in range(len(odds)):
        if ifprimary_num(even+odds[i]) and not visit[i]: #not l[i] l列表的第i个元素是空的
            visit[i]=1
            if not p[i] or match(p[i],visit,p,odds):
                p[i]=even
                return True
    return False
            

while 1:
    try:
        n=int(input())
        s=list(map(int,input().split()))
        #print(s)
        evens,odds=[],[]
        for i in s:
            if i%2==0:
                evens.append(i)
            else:
                odds.append(i)
        #print(even,odd)
        p=[0]*len(odds)
        cnt=0 
        for even in evens:
            visit=[0]*len(odds)  #每次循环的visit都要清空
            if match(even,visit,p,odds): 
                cnt += 1            
        print(cnt)

    except:
        break