题解 | #HJ28 素数伴侣#

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

def match_odd(odds, flags, result, even):
    for i, odd in enumerate(odds):
        if check_prime(even+odd) and (flags[i]==False):
            flags[i] = True
            if (result[i]==False) or match_odd(odds, flags, result, result[i]):
                result[i] = even
                return True
    return False

while True:
    try:
        n = int(input())
        nums = [int(i) for i in input().split()]
        evens = [i for i in nums if i%2==0]
        odds = [i for i in nums if i%2!=0]
        if (not evens) or (not odds):
            print(0)
            continue
        count = 0
        result = [0] * len(odds)
        for even in evens:
            flags = [False] * len(odds)
            if match_odd(odds, flags, result, even):
                count += 1
        print(count)
    except:
        break