Python题解 | #素数伴侣#二分图匈牙利算法

import sys
import math


def is_prime(x):
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True


def find(odd, visited, choose, evens):
    for j, even in enumerate(evens):
        if is_prime(odd + even) and not visited[j]:
            visited[j] = True
            if choose[j] == 0 or find(choose[j], visited, choose, evens):
                choose[j] = odd
                return True
    return False


while True:
    try:
        n = int(input())
        list1 = list(map(int, input().split(' ')))
        odds = []
        evens = []
        count = 0
        for i in list1:
            if i % 2 == 0:
                odds.append(i)
            else:
                evens.append(i)
        if len(odds) == 0 or len(evens) == 0:
            print(count)
            break
        choose = [0] * len(evens)
        for odd in odds:
            visited = [False] * len(evens)
            if find(odd, visited, choose, evens):
                count += 1
        print(count)
    except:
        break