题解 | #素数伴侣#

# # import math

# # def is_prime(a, b):
# #     absum = a + b
# #     for i in range(2, int(math.sqrt(absum)+1)):
# #         if absum % i == 0:
# #             return 0
# #     return 1

# # def match(i):
# #     for j in range(n):
# #         if array[i][j] == 1 and not visited[j]:
# #             visited[j] = True
# #             if match(j) == -1 or match(matched[j]):
# #                 matched[j] = i
# #                 return True
# #     return False

# # num = int(input())
# # data = list(map(int, input().split()))
# # evens = []
# # odds = []
# # for i in data:
# #     if i % 2 == 0:
# #         evens.append(i)
def is_prime(x):
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return 0
    return 1

def match(i):
    for j in range(m):
        if array[i][j] == 1 and not visited[j]:  # 第j个偶数还没有进行配对，且没被访问过
            visited[j] = True  # 访问第j个偶数
            # 配对成功标准（或）：
            # 1、先到先得。该偶数还没有进行配对。
            # 2、能让则让。该偶数虽然进行配对了，但与其配对的奇数能够找到另外的偶数进行配对。
            if matched[j] == -1 or match(matched[j]):  # 这里用到了递归的思想
                matched[j] = i  # 将该偶数与奇数进行配对
                return True  # 配对成功
    return False

n = int(input())
a = list(map(int, input().split()))
odds = []  # 分奇偶数，素数伴侣必为一奇一偶
evens = []
for data in a:
    if data % 2 == 0:
        evens.append(data)
    else:
        odds.append(data)
n = len(odds)
m = len(evens)
array = [[-1 for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        array[i][j] = is_prime(odds[i] + evens[j])
# print(array)
matched = [-1 for i in range(m)]  # 记录每一个偶数匹配的奇数
for i in range(n):
    visited = [False for k in range(m)]
    match(i)
print(len(matched) - matched.count(-1))