题解 | #素数伴侣#

import math

#判断是否为素数
def check(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num % i ==0:
            return False
    return True

#配对过程
def find(odd, choose, visited, evens):
    #enumerate取得下标以及对应偶数元素，下标可以表示当前奇数与哪个下标的偶数配对
    for j,even in enumerate(evens):
        if check(odd+even) and not visited[j]: #如果当前奇数和偶数的和是素数，那么查看当前偶数是否被匹配过，没有匹配过，那么将这个偶数与当前奇数的匹配条件设置为True
            visited[j] = True
            #如果当前偶数没有与之前的奇数已经连接上，即choose对应下标依旧为0，而不是连接上的奇数，则可以直接匹配(将choose对应下标的值替换为当前奇数)，如果choose对应的下标不为0，已经有对应的奇数，那么之前连接的对应奇数重新使用find寻找另外可匹配的偶数，寻找到
            #则与现在偶数断开连接，与另外可匹配的偶数连接
            if choose[j] == 0 or find(choose[j],choose,visited,evens):
                choose[j] = odd
                #返回True表示匹配成功
                return True
    return False

while True:
    try:
        n = int(input())
        #获取输入元素列表
        l = list(map(int,input().split()))
        #奇数列表
        odds = []
        #偶数列表
        evens = []
        #记录配对数量
        count = 0
        for i in l:
            if i % 2 ==0:
                evens.append(i)
            else:
                odds.append(i)
        #查询奇数与之配对的偶数
        #choose用来存放奇数与之相同下标的偶数，即为连接一对
        choose =[0]*len(evens)
        for odd in odds:
            #visited用来查看当前奇数可以和哪个偶数可以进行配对，True表示有配对的条件
            visited = [False]*len(evens)
            if find(odd,choose,visited,evens):
                count +=1
        print(count)
    except:
        break