题解 | #素数伴侣#

from os import error
import sys
import math
#函数1：判断是否素数，输入为一个正整数，输出为1(是素数)或0(非素数)
#2是素数，对于任何>=3的正整数n，从3到int(sqrt(n))+1遍历去整除n，如果存在余数都是0，则n非素数。反之则n为素数
def isprime(n):   
    if n == 2:
        res = 1
    for i in range(3,int(math.sqrt(n)) + 1):
        if n % i == 0:
            return 0
    return 1
#函数2：计算能形成奇偶的全组合。输入：奇数列表和偶数列表，输出为数值笛卡尔积的是否值。
def prime_dic(odds,evens):
    dic = {}
    for o in odds:
        for e in evens:
            if isprime(o + e):
                dic[f"{o},{e}"] = 1
            else:
                dic[f"{o},{e}"] = 0
    return dic
#函数3：关键函数，找到最大路径。
#输入值：
#--某固定奇数o
#--全部偶数列表evens
#--各个奇数的配对偶数列表(初始值为0或空)choose
#--各个奇数是否被访问(初始值为0或空)visited
#--由prime_dic生成的奇偶列表组合字典dic
#输出值：
#--1(能够配对)或0(不能配对)
#原理和写法：
#对于给定的奇数o，遍历各个偶数e in evens。
#各个偶数的配对列表choose初始值全为0或空，且是否被访问列表同样为0或空。
#此时，如果o和e能够配对成功，且e没有被访问过，那么就将偶数e对应的visited值改为1(已被访问)。如果choose值为0或空，则将该值改为o。
#经过e在evens中遍历与o尝试配对，就可能出现若干个e<n>,e<m>,e<k>...对应的visited值为1，choose值全为o.
#然后对于下一个奇数oo，先将访问列表归0。与oo能够配对的奇数记为e<a>,e<b>...，若其中存在与上一个奇数o已经配对的偶数，不妨记为e<k>。(若本轮不存在，一直继续，总会存在，否则为简单解)
#由于此时e<k>的访问值在oo配对过程中已经被改为1，其他e<n>的访问值还是0。则再执行一次:e<k>上一个配对成功的奇数o与全部偶数的配对尝试,就意味着寻找o是否能和除了e<k>之外的其他偶数e<j>配对。
#如果有能够配对的e<j>，那么e<k>的choose值从o改到oo，而e<j>的choose值变成了o，同时配对计数+1。如果没有这样的e<j>了，那么e<k>的choose值保持不变，还是o。
#这样，经过对所有奇数循环操作后，就能找到最多的配对数量。
def find(o,evens,choose,visited,dic):
    for j,e in enumerate(evens):
        if (dic[f"{o},{e}"] == 1) and (visited[j] == 0):
            visited[j] = 1
            if (choose[j] == 0) or (find(choose[j],evens,choose,visited,dic) == 1):
                choose[j] = o
                return 1
try:
    n = int(input())
    lst = list(map(int,input().split(" ")))
    odds = [x for x in lst if x % 2 == 1]
    evens = [x for x in lst if x % 2 == 0]
    cnt = 0
    dic = prime_dic(odds,evens)
    choose = [0]*len(evens)
    for o in odds:
        visited = [0]*len(evens)
        if find(o,evens,choose,visited,dic):
            cnt += 1
    print(cnt)
except Exception as e:
    print(e)