题解 | #素数伴侣#

def is_prime(num):
    if num<2:
        return False
    i = 2
    while i*i<=num:
        if num%i==0:
            return False
        i+=1
    return True
     
def find(odd, evens, visited, selected):
    for i, even in enumerate(evens):
        if is_prime(even+odd) and not visited[i]:
            visited[i]=True  
            # 如果当前偶数没有对象（0），那么就与之组合
            # 就尝试为 selected[i] 协调新对象
            if selected[i] == 0 or find(selected[i],  evens, visited, selected):
                selected[i]=odd
                return True
    # 没有对象
    return False
 
while True:
    try:
        n=int(input())
        nums=list(map(int,input().split(' ')))
        
        # 准备分组
        evens, odds=[], []
        for num in nums:
            if num%2==0:
                evens.append(num)
            else:
                odds.append(num)

        # 尝试为每个奇数匹配偶数        
        selected=[0]*len(evens)    # 记录与第 i 个偶数匹配的奇数
        result = 0
        for odd in odds:
            visited=[0]*len(evens) # 记录访问过的偶数，防止重复访问
            if find(odd, evens, visited, selected):
                result +=1 #匹配成功就把结果+1
        print(result)
    except:
        break