题解 | #素数伴侣#

import math

def check_prime(num):
    for i in range(2, int(math.sqrt(num)+1)):
        if num%i == 0:
            return False
    return True

def find_even(odd, evens, choose, visited):
    for j, even in enumerate(evens):
        if check_prime(odd + even) and not visited[j]:
            visited[j] = True
            # 假设第j个 位置的evens还没有被choose；
            # 或者被choose了，但是之前choose它的odd可以选择一个新的even。
            # 那么当前odd可以选择第j个even。
            if choose[j]==0 or find_even(choose[j], evens, choose, visited):
                choose[j] = odd
                return True
    return False

N = int(input().strip())
all_nums = list(map(int, input().strip().split()))
odds = []  # 奇数集合
evens = []  # 偶数集合
for num in all_nums:
    if num%2 == 0:
        evens.append(num)
    else:
        odds.append(num)

count = 0
choose = [0]*len(evens)
for odd in odds:
    visited = [False]*len(evens)
    if find_even(odd, evens, choose, visited):
        count += 1

print(count)