题解 | #素数伴侣#

def isprime(n):  # 判断是不是质数
    if n == 2:
        return 1
    if n == 1:
        return 0
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return 0
        else:
            return 1


def match(i):
    """
    迭代,增加匹配
    :param i: 奇数索引
    :return: 无法匹配0
             新匹配1
             打破旧匹配新增匹配1
    """
    for j in range(len(lst02)):
        if lst_u[j] == 0 and isprime(lst01[i] + lst02[j]):
            lst_u[j] = 1  # 本次循环连线上锁
            if lst_m[j] < 0 or match(lst_m[j]):
                lst_m[j] = i
                return True
    return False


if __name__ == "__main__":
    n = int(input())
    lst = list(map(int, input().split()))
    lst01 = []  # 奇数
    lst02 = []  # 偶数
    for i in lst:
        if i % 2 == 1:
            lst01.append(i)
        else:
            lst02.append(i)
    lst_m = [-1] * len(lst02)
    count = 0  # 计数器
    for i in range(len(lst01)):
        # 旧的被赶走后不能抢新来的
        lst_u = [0] * len(lst02)
        if match(i):
            count += 1
    print(count)