题解 | #素数伴侣#

n=int(input())
num=list(map(int,input().split()))
def isprime(a,b):#判断相加是否为素数
    sum=a+b
    if sum<2:
        return False
    elif sum<4:
        return True
    elif sum%2==0 or sum%3==0:
        return False
    i=5
    while i*i<sum:
        if sum%i==0 or sum%(i+2)==0:
            return False
        i+=6
    return True
#获得二维矩阵a[i][j],i，j代表第几个数，对应矩阵内元素全为1或0，1表示相加为素数
a=[]
for i in num:
    b=[]
    for j in num:
        if isprime(i,j):
            b.append(1)
        else:
            b.append(0)
    a.append(b)
#第i个数是否能找到对应parter相加为素数
def find(a,i,parter,seen):
    for j in range(len(a)):
            if a[i][j] and not seen[j]:
                seen[j]=True #是否访问过该数，防止重复访问陷入循环
                if parter[j]==-1 or find(a,parter[j],parter,seen):
                    parter[j]=i
                    parter[i]=j
                    return True
    return False

parter=[-1]*len(a)
count=0
for i in range(len(a)):
    seen=[False]*len(a)
    if parter[i]==-1:
        if find(a,i,parter,seen):
            count+=1
print(count)