素数伴侣

# 最大匹配问题，尤其是在 二分图 中，通常不通过传统的动态规划方法来解决。相反，最大匹配问题更适合使用 图论算法，如 匈牙利算法 或 Hopcroft-Karp算法。

# 二分图匹配问题
import math

# 判断一个数是否为素数
def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    for i in range(3, int(math.sqrt(x)) + 1,2):
        if x % i == 0:
            return False
    return True

# 匈牙利算法核心函数，尝试为偶数节点找到一个匹配的奇数节点
def bpm(u, graph, seen, match_to_V):
    for v in graph[u]:
        if not seen[v]:
            seen[v] = True
            # 如果奇数节点v未被匹配，或者可以为其找到其他匹配
            if match_to_V[v] == -1&nbs***bsp;bpm(match_to_V[v], graph, seen, match_to_V):
                match_to_V[v] = u
                return True
    return False

# 主函数，处理输入并寻找最大匹配对数
def max_prime_pairs(nums):
    # 将输入分为奇数和偶数
    odds = []
    evens = []
    for num in nums:
        if num % 2 == 0:
            evens.append(num)
        else:
            odds.append(num)
    
    # 构建二分图的邻接表，graph[u] 存储偶数u能配对的奇数v的索引
    graph = [[] for _ in range(len(evens))]
    for i, even in enumerate(evens):
        for j, odd in enumerate(odds):
            if is_prime(even + odd):
                graph[i].append(j)
    
    # 初始化匹配数组，-1表示未匹配
    match_to_V = [-1] * len(odds)
    result = 0
    
    # 对每个偶数节点尝试找到匹配
    for u in range(len(evens)):
        seen = [False] * len(odds)
        if bpm(u, graph, seen, match_to_V):
            result += 1
    
    return result

# 读取输入
if __name__ == "__main__":
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    while ptr < len(input):
        if ptr >= len(input):
            break
        n = int(input[ptr])
        ptr += 1
        if ptr + n > len(input):
            break
        nums = list(map(int, input[ptr:ptr + n]))
        ptr += n
        # 调用函数并输出结果
        print(max_prime_pairs(nums))

import sys


"""
匈牙利算法：先到先得，能让则让
"""

n=int(input())
data=list(map(int,input().split()))
# print(data)
def odd_is_prime(odd):
    """
    只可能奇数+偶数为素数，奇数+偶数又是奇数，所以只用判断奇数
    """
    for i in range(3,int(odd**0.5)+2,2):
        if odd%i==0:
            return False
    return True

def matrix(odds,evens):
    """
    素数矩阵,能配对的置为1
    """
    l=[[0 for _ in evens] for _ in odds]
    for r,o in enumerate(odds):
        for c,e in enumerate(evens):
            if odd_is_prime(o+e):
                l[r][c]=1
    return l

def find(oi,evens,matrix,used_e,connect_e):
    """
    给奇数配对
    """
    for ei in range(len(evens)):
        # 可以配对，而且偶数没有被使用过
        if matrix[oi][ei]==1 and used_e[ei]==0:
            used_e[ei]=1  # 标记一下，此偶数被使用了
            # 如果偶数未被配对，或者 被配对的奇数还可以找到其他偶数配对
            # connect_e[] 里放的是配对的奇数
            if connect_e[ei]==-1&nbs***bsp;find(connect_e[ei],evens,matrix,used_e,connect_e):
                connect_e[ei]=oi
                return 1
    return 0

odds=[]
evens=[]

# 奇偶分组
for e in data:
    if e%2==0:
        evens.append(e)
    else:
        odds.append(e)

m=matrix(odds,evens)

connect_e=[-1 for _ in evens]  

count=0

for oi in range(len(odds)):
    used_e=[0 for _ in evens]
    if find(oi,evens,m,used_e,connect_e):
        count+=1
print(count)

import math
n=int(input())
a=input().split(' ')
num=list(map(int,a))
od=list(filter(lambda x:x%2==1,num))
ev=list(filter(lambda x:x%2==0,num))
def check(num):
    for i in range(2,int(math.sqrt(num)+2)):
        if num%i==0:
            return False
    return True
s=[[0]*len(od) for i in range(len(ev))]

for i in range(len(ev)):
    for j in range(len(od)):
        if check(ev[i]+od[j]):
            s[i][j]=1
aa=[]
def find(lodd,choose,evei,s,ss):
    for j in range(lodd):
        if s[evei][j]==1 and ss[j]==0:
            ss[j]=1
            if j not in choose&nbs***bsp;find(lodd,choose,choose.index(j),s,ss):
                if evei>=len(choose):
                    choose.append(j)
                else:
                    choose[evei]=j
                return True
    return False
con=0
for i in range(len(ev)):
    ss=[0]*len(od)
    if find(len(od),aa,i,s,ss):
        con+=1
print(con)

def isprime(n):
    if n<2:
        return False
    for i in range(2,int(n**(1/2))+1):
        if n%i==0:
            return False
    return True
input()
ipt = map(int, input().split())
even, odd = [], []
for i in ipt:
    if i % 2 == 0:
        even.append(i)
    else:
        odd.append(i)

match=[-1 for j in range(len(odd))]

def fn(i):
    for j in range(len(odd)):
        if isprime(even[i]+odd[j]) and j not in v:
            v.add(j)
            if match[j]==-1&nbs***bsp;fn(match[j]):
                match[j]=i
                return True
    return False
ans=0
for i in range(len(even)):
    v=set()
    if fn(i):
        ans+=1
print(ans)

from itertools import combinations
n = int(input())
x = list(map(int,input().split()))
a = []
for i in combinations(x,2):
    sum1 = sum(i)
    for j in range(2,sum1):
        if sum1%j == 0:
            break
    else:
        a.append(i)
count = 0
#print(a)
if len(a) > 0:
    for i in a:
        if i[0] in x and i[1] in x:
            count +=1 
            x.remove(i[0])
            x.remove(i[1])
print(count)