题解 | #素数伴侣#

def is_prime(x):
    for i in range(2,int(math.sqrt(x)+2)):##如果只+1那么当x=2时，就会出现range(2,2)
        if x%i==0:
            return False
    return True

def prime_dic(odds,evens):##建立一个伴侣字典，通过查字典就可以知道是否可以称为伴侣，这样就不必重复计算
    dic ={}
    for odd in odds:
        for even in evens:
            if is_prime(odd+even):
                dic['%d,%d'%(odd,even)]=1
            else:
                dic['%d,%d'%(odd,even)]=0
    return dic

def find(odd,evens,choose,visited):##最难以理解的一步，只能通过带入简单例子去理解，每个参数都至关重要
    for j,even in enumerate(evens):
        if dic['%d,%d'%(odd,even)]==1 and not visited[j]:
            visited[j]=True
            if choose[j]==0 or find(choose[j],evens,choose,visited):
                choose[j]=odd
                return True

while True:
    try:
        n = int(input())
        num = list(map(int,input().split()))
        odds=[]
        evens=[]
        count=0
        for i in num:
            if i%2==0:
                evens.append(i)
            else:
                odds.append(i)
        dic = prime_dic(odds,evens)
        choose=[0]*len(evens)
        for i in odds:
            visited=[False]*len(evens)
            if find(i,evens,choose,visited):
                count+=1
        print(count)
    except:
        break