题解 | #素数伴侣#

import sys
from copy import deepcopy
from collections import defaultdict

# 生成素数列表
isprime = [1 for i in range(60001)]
# 匈牙利算法，先到先得能让就让
# 有机会上，没机会创造机会也要上
used = []  # 偶数是否使用过
# 奇偶分组
odd = []
even = []
evenForOdd = defaultdict(int)


def find(i):
    for j in even:
        if isprime[i + j] and used[j] == 0:
            used[
                j
            ] = 1  # 这个标志位表示当前i，j正在试图在一起，其他人别来打扰。没有这个标志位，每个人在递归的时候都会来询问，这样for循环就走不完了
            # 判断j是否名花有主
            if evenForOdd[j] == 0:  # 这个偶数没有主（匹配奇数）
                evenForOdd[j] = i  # 赶紧占住
                return True  # 表示该奇数已经找到偶数，计数加一
            else:  # 名花有主
                if find(evenForOdd[j]):  # 能让则让
                    evenForOdd[j] = i  # 这个坑归你了
                    return True
                # else 下一个更好！


if __name__ == "__main__":
    # 输入
    n = int(input())
    line = list(map(int, input().split()))

    # isprime[2] = 1
    i = 2
    while i < 60001:
        if isprime[i] == 1:
            for j in range(i + i, 60001, i):
                isprime[j] = 0
        i += 1

    for i in line:
        if i % 2 == 0:
            even.append(i)
        else:
            odd.append(i)
    s = 0  # 计数
    for i in odd:
        used = [0 for i in range(60001)]
        if find(i):
            s += 1

    print(s)

#回溯在测试数据多的时候会超时
# track = []
# # tracks = []
# res = 0
# used  = [0 for i in range(30001)]
# def backtrack():
#     global res
#     if len(track) > res :
#         res = len(track)


#     for o in odd:
#         if used[o] == 1:
#             continue
#         track.append(o)
#         used[o] = 1
#         for e in even:
#             if used[e] == 1:
#                 continue
#             if isprime[o+e] != 1:
#                 continue
#             track.append(e)
#             used[e] = 1
#             backtrack()
#             used[e] = 0
#             track.pop()
#         used[o] = 0
#         track.pop()

# backtrack()

# print((res//2))