题解 | #素数伴侣#

import sys


def get_prime(x):
    for i in range(3,int(x**0.5)+2,2):
        if x%i == 0:
            return False
    return True

def get_group(x):
    odds,evens = [],[]
    for i in x:
        if i%2 == 0:
            evens.append(i)
        else:
            odds.append(i)
    return odds,evens

#遍历偶数列表，查看奇数与偶数的和是否为奇数，其中vis列表主要用于临时储存当前素数与遍历的偶数列表的配对情况，connect列表用于存储最终每个偶数对应的奇数
#因此每次循环时vis需要重新创建
def find(evens,vis,connect,odd):
    #遍历偶数列表，因为需要同时用到下标索引和值，所以使用enumerate函数
    for i,even in enumerate(evens):
        if get_prime(odd + even) and vis[i] == 0:
            vis[i] = 1          #进行标记，标记该偶数可以和入参奇数进行配对
            #判断这个偶数没有配对过或者他配对的奇数可以和其他偶数进行配对（这个其他奇数是存储在connnet这个列表中的），进行递归
            if connect[i] == 0 or find(evens,vis,connect,connect[i]):
                connect[i] = odd           #将这个奇数存入connect中表示该奇数和该偶数配对成功
                return True
    return False

while True:
    try:
        N = int(input())
        list1 = list(map(int,input().split()))
        #print(list1)
        odds,evens = get_group(list1)
        count1 = 0
        #connect列表元素个数需要与偶数个数一样，这样才能将每个偶数与奇数配对情况一一对应表现出来
        connect = [0]*len(evens)
        #遍历奇数列表
        for odd in odds:
            #需要在循环内串讲vis列表，这样才能每个vis对应一个入参奇数odd
            vis = [0]*len(evens)
            if find(evens,vis,connect,odd):
                count1 += 1
        print(count1)
    except:
        break