题解 | #素数伴侣#

#判断是否素数
def isprime(n: int):
    ret = 1
    if n == 1 or n != 2 and n % 2 == 0:
        ret = 0
    else:
        for i in range(3, int(n**0.5) + 1, 2):
            if n % i == 0:
                ret = 0
                break
    return ret
#匈牙利算法匹配,先到先得,能让则让
#p[]表示b中元素对应a中匹配元素下标
#used 对a中元素进行匹配时b中元素访问情况

#在对a中元素i的本轮匹配中, 本轮匹配是指能让则让的迭代寻找
#used[j] = 1
#1.假设b中元素j被i占用,那么如果原来j对应的a中元素找不到新的匹配位置
#  本轮匹配j是让不出来的
#2.假设b中元素j被i占用,那么如果原来j对应的a中元素能让出来
#  如果后续是不可以的,那么同1.本轮匹配j让不出来
#  如果后续也是可以的,那么i可以真实占用j

#  =>总之两种情况一种让不出来 保持原匹配,一种让的出,被本层迭代占用
# 让的出 iscmp = True 让不出 iscmp= False
#  所以,在本轮匹配中,只要j 被进行过匹配的尝试,下一层迭代中即无法被使用

def iscmp(i):
    for j in range(b_len):
        if used[j]==0 and isprime(odd[i]+even[j]):
            used[j] = 1
            if p[j]<0 or iscmp(p[j]):
                p[j]=i
                return True

    return False



while  True:
    try:
        
        n = int(input())
        num = list(map(int,input().split()))
        odd,even=[],[]

        for x in num:
            if x%2==1:
                odd.append(x)
            else:
                even.append(x)

        a_len = len(odd)
        b_len = len(even)



        p = [-1]*b_len

        cnt = 0
        for i in range(a_len):
            used = [0]*b_len
            if iscmp(i):
                cnt +=1


        print(cnt)       

    except:
        break