素数伴侣

def is_zhi(n):
    for i in range(2, int(n**0.5)+1):
        if not n % i:
            return False
    return True


def find_pair(n, even, visited, match):
    for i, e in enumerate(even):
        if is_zhi(n+e) and not visited[i]:
            visited[i] = True
            if not match[i]&nbs***bsp;find_pair(match[i], even, visited, match):
                match[i] = n
                return True
    return False


while True:
    try:
        n, nums = int(input()), list(map(int, input().split()))
        odd, even = [], []
        for i in nums:
            if i % 2:
                odd.append(i)
            else:
                even.append(i)
        match = [0] * len(even)
        for n in odd:
            find_pair(n, even, [False]*len(even), match)
        
        print(len(match) - match.count(0))
    except:
        break

def isPrime(n:int):
    if n <= 3:
        return True
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# visited 递归的最外层 也就是新来的小哥哥给小姐姐打上他自己的印记
# choose 指示小姐姐的男朋友是谁
def findAddPath(odd:int, evens:list, visited:list, choose:list):
    for j,even in enumerate(evens): # 扫描每个小姐姐
        # 小哥哥喜欢小姐姐 且 新来的小哥哥给 小姐姐标记
        if isPrime(odd + even) and not visited[j]:
            visited[j] = True # 小姐姐被新来的小哥哥抢走了
                                   # choose[j] 小姐姐原来的男朋友只能重新找别人了
                                   # 下次递归时候，visited 为 True，这个小姐姐被后来者抢了
                                   # 只能遍历下一个小姐姐了
            if (choose[j] == 0)&nbs***bsp;(findAddPath(choose[j], evens, visited, choose)):
                choose[j] = odd    # 将小哥哥分给小姐姐
                return True
    return False
    
while True:
    try:
        n, nlist = int(input()), map(int, input().split())
        odds, evens = [], []
        count = 0
        # 分类 奇数(小哥哥) 和 偶数(小姐姐)
        for i in nlist:
            if i % 2:
                odds.append(i)
            else:
                evens.append(i)
        choose = [0] * len(evens)
        for odd in odds:
            # 对于每一个小哥哥， 他可以搭讪任何所有小姐姐
            # 因为匈牙利算法规定 小哥哥有抢小姐姐的权利
            # visited 标记的意思就是 给小姐姐打上 我的印记
            # 张三来了，不管三七二十一，就把他喜欢的小姐姐打上张三的印记，李四就打李四的印记
            # 之后 张三和小姐姐聊天，发现她有男朋友了，那就递归，让她的男朋友去找别人
            # 进入递归后，不可能再匹配这个小姐姐了，因为这个小姐姐在上层递归，被新来的打印记了
            # 于是，被赶走的小哥哥只能往后找其他小姐姐了
            visited = [False] * len(evens)
            if findAddPath(odd, evens, visited, choose):
                count += 1
        print(count)
    except:
        break

def PrimeNumber(x):
    """判断一个数是否为素数（质数）"""
    if x < 2:
        return False
    else:
        for j in range(2, x):
            if x % j == 0:
                return False

        else:
            # print(x)
            return x


n = input()
n_list = list(map(int, input().strip().split()))  # 输入n个整数
odd = []  # 定义一个奇数列表
i = 0
while i < len(n_list):
    if n_list[i] % 2 == 0:
        i += 1
    else:
        n_list.pop(i)  # 将奇数弹出并放入奇数列表中
        odd.append(i)

list1 = []
count = 0
# 两个列表中的所有数进行组合配对
for a in n_list:
    for b in odd:
        list1.append((a, b))
for m in list1:
    s = m[0] + m[1]
    if PrimeNumber(int(s)):
        count += 1
print(count)

'''
匈牙利算法（求二分图的最大匹配）：要用到递归，思想：后来者居上
'''
# 1、判断是否是素数 (若在1到该数平方根之间都没有可除尽的数)
def isprime(num):
    if num<=3: return True
    for i in range(2,int(num**0.5)+1):
        if not num%i: return False
    return True
    
(2485)# 2、寻找“增广路径”（这个数可否匹配，该跟谁连）
def find(odd, visited, choose, evens):
    for j,even in enumerate(evens):  # 扫描每个待被匹配的even
        if isprime(odd+even) and not visited[j]:
            visited[j] = True
            if choose[j]==0&nbs***bsp;find(choose[j],visited,choose,evens):
            (2486)# 如果第j位even还没被人选 或者 选它的那个odd还有别的even可以选择 那就把这位even让给当前的odd
                choose[j] = odd
                return True # 说明匹配
    return False

(2487)# 3、开始odd先生和even小姐们入场，并各自到自己队列，开始匹配
while True:
    try:
        n = int(input())
        nums = list(map(int,input().split(' ')))
        count = 0
        # 奇数+奇数 = 偶，偶+偶=奇数，都不能成为素数。只能奇数+偶数的组合才有可能
        odds,evens = [],[] (2488)# 把数分为奇数和偶数
        # so，每次拿一个数，到对应的list中去找
        for num in nums:
            if num%2: odds.append(num)
            else: evens.append(num)
                
        (2489)# now 对每个odd,去找自己的even
        choose = [0]*len(evens)  # 装 来匹配这位even的对应的odd先生
        for odd in odds:
            visited = [False]*len(evens)  (2490)# 每一次要清零（对每个待去匹配的odd来说，每个even都是新鲜的
            if find(odd, visited, choose, evens):
                count += 1
        print(count)

    except:
        break