题解 | #素数伴侣，匈牙利算法python3版本#

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):  # i表示第几行，左侧元素
    for j in range(n):  # j表示第几列，右侧元素
        if array[i][j] == 1 and not visited[j]:  # 有边且未访问
            visited[j] = True  # 记录状态为访问过
            if matched[j] == -1 or match(matched[j]):  # 如果该右侧元素暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
                matched[j] = i  # 当前左侧元素成为当前右侧元素的新匹配
                return True
    return False  # 循环结束，仍未找到匹配，返回匹配失败

while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
    except:
        break
    else:
        evens, odds = [], []
        for i in a:  # 对偶数和奇数进行分组。偶数加奇数才有可能是质数
            if i % 2 == 0:
                evens.append(i)
            else:
                odds.append(i)

        # 求关于是否是prime的矩阵，即得到邻接矩阵
        m = len(odds)  # 行，左侧元素
        n = len(evens)  # 列，右侧元素
        array = [[-1 for i in range(n)] for j in range(m)]
        for i, x in enumerate(odds):  # odds和evens谁先谁后无所谓
            for j, y in enumerate(evens):
                array[i][j] = is_prime(x + y)

        # 开始匈牙利算法，进行匹配
        matched = [-1 for i in range(n)]  # 记录当前已匹配的右侧元素(列)所对应的左侧元素(行)
        counter = 0
        for i in range(m):
            visited = [False for k in range(n)]  # 记录右侧元素是否已被访问过。每切换左侧元素时进行重置。
            if match(i):
                counter += 1
        print(counter)