题解 | #素数伴侣#

def isprime(num):
    if num<=3: return True
    for i in range(2,int(num**0.5)+1):
        if not num%i: return False
    return True

def find(odd, visited, choose, evens):
    for j,even in enumerate(evens):  # 扫描每个待被匹配的even
        if isprime(odd+even) and not visited[j]:
            visited[j] = True
            if choose[j]==0 or find(choose[j],visited,choose,evens):
            # 如果第j位even还没被人选 或者 选它的那个odd还有别的even可以选择 那就把这位even让给当前的odd
                choose[j] = odd
                return True # 说明匹配
    return False

while True:
    try:
        n = int(input())
        nums = list(map(int,input().split(' ')))
        count = 0
        # 奇数+奇数 = 偶，偶+偶=奇数，都不能成为素数。只能奇数+偶数的组合才有可能
        odds,evens = [],[] # 把数分为奇数和偶数
        for num in nums:
            if num%2: odds.append(num)
            else: evens.append(num)
        
        choose = [0]*len(evens)  # 装 来匹配这位even的对应的odd先生
        for odd in odds:
            visited = [False]*len(evens)  # 每一次要清零（对每个待去匹配的odd来说，每个even都是新鲜的
            if find(odd, visited, choose, evens):
                count += 1
        print(count)
    except:
        break