题解 | 素数伴侣

def  is_prime(num):
    if num <= 3:
        return num > 1
    for i in range(2, int(num ** 0.5) + 1):
        if num%i == 0:
            return False
    return True


def get_match(i):
    for j in range(n):
        if (array[i][j]==True) and (visit[j]==False):
            visit[j] = True
            if matchedNum[j] == -1 or get_match(matchedNum[j]):
                matchedNum[j] = i
                return True
    return False


while True:
    try:
        num = int(input())
        lst = list(map(int, input().split()))
        odds, evens = [], []
        for i in lst:
            if i % 2 == 0:
                evens.append(i)
            else:
                odds.append(i)
    
        m, n = len(odds), len(evens)

        array = [[-1 for i in range(n)] for j in range(m)]
        count = 0
        for i,x in enumerate(odds):
            for j,y in enumerate(evens):
                array[i][j] = is_prime(x+y)

        matchedNum = [-1 for i in range(n)]

        for i in range(m):
            visit = [False for i in range(n)]
            if get_match(i):
                count += 1
        print(count)

    except:
        break