素数伴侣

#!/user/local/bin/python3
import math
def is_prime(num):   #判断是否是质数
    if num<2:
        return False
    if num==2:
        return True
    pnum=int(math.sqrt(num))+1
    for i in range(2,pnum):
        if num%i==0:
            return False
    return True

def find_element(eles,target):  ##查找元素在列表中第一次出现的索引，没有找到返回-1
    for i in range(len(eles)):
        if eles[i].count(target) > 0:
            return i
    return -1

def takeSecond(elem):
    return elem[1]

strnumbs=int(input())
sources=list(map(int,input().split()))

#思路：除了2，所有的质数都是一个奇数+一个偶数，所以可以分成两个队列进行配对。
#双重循环，找出所有元素所有可能的配对情况，有一个配对加一分。按照分数，从低到高排序。所有可能的配对结果放在配对池子中。
#1.分数为0的元素不能配对，从分数排行榜中删除。
#2.优先满足分数少的元素形成配对，配对以后，配对结果放在成果池子中，配对结果从配对池子中删除，配对的两个元素的分数都减一。
#3.如果数字X放入成果池子中的次数等于X在原始列表中的数量（考虑X在原始列表中有重复的情况），清空配对池子中所有包含X的配对，将X的分数清零。
#刷新分数排行榜，重复上述（1）（2）（3）步骤，直到分数排行榜为空或配对池子为空。

#除了2，所有的质数都是一个奇数+一个偶数，所以可以分成两个队列
odd=[item for item in sources if item%2!=0]  #奇数队列
even=[item for item in sources if item%2==0]  #偶数队列
odd.sort()
even.sort()

final_result=[]     #成果池子
backup_result=[]   #配对池子
sourcelist=[[elem,0,0] for elem in sources] #分数排行榜，第二列代表配对分数，第三列代表是否已经放入成果池子

##初始化分数排行榜
for i in range(len(odd)):
    for j in range(len(even)):
        if is_prime(odd[i]+even[j]): ##找到配对
            backup_result.append([odd[i],even[j]])
            sourcelist[find_element(sourcelist,odd[i])][1]+=1
            sourcelist[find_element(sourcelist,even[j])][1]+=1
sourcelist.sort(key=takeSecond)

i=0
while i < len(sourcelist) and len(backup_result)>0:
    if sourcelist[i][1]==0:
        sourcelist.pop(i) ##删除分数排行榜中无法配对的元素
        continue
    else:
        while sourcelist[i][1]>0:
            ##找到第一个配对的元素的在配对池子中的索引
            xindex=find_element(backup_result,sourcelist[i][0])
            ##找到第一个配对中另一个元素在分数排行榜中的索引
            if sourcelist[i][0]%2==0:
                another_index=find_element(sourcelist,backup_result[xindex][0])
            else:
                another_index=find_element(sourcelist,backup_result[xindex][1])
            sourcelist[i][1]-=1 ##配对的第一个元素，分数减一
            sourcelist[another_index][1]-=1 ##配对的第二个元素，分数减一
            final_result.append(backup_result[xindex]) ##将配对结果放入成果池子中
            sourcelist[i][2]=1 ##记录该元素放入成果池子中的次数
            sourcelist[another_index][2]=1 ##记录该元素放入成果池子中的次数
            backup_result.pop(xindex) ##删除配对池子中的该配对

            #如果元素X放入成果池子中的次数等于X在原始列表中的数量（考虑X在原始列表中有重复的情况），清空配对池子中所有包含X的配对，将X的分数清零。
            if sourcelist[i][2] == sources.count(sourcelist[i][0]):
                while find_element(backup_result,sourcelist[i][0])!=-1: 
                    popone=backup_result.pop(find_element(backup_result,sourcelist[i][0])) #清空配对池子中所有包含X的配对
                    find_index=find_element(sourcelist,popone[0]) ##清空配对的时候，对应的元素分数减一
                    sourcelist[find_index][1]-=1
                    find_index2=find_element(sourcelist,popone[1])
                    sourcelist[find_index2][1]-=1
                sourcelist[i][1]=0 ##X的分数清零，不再参与配对

            if sourcelist[another_index][2] == sources.count(sourcelist[another_index][0]):
                while find_element(backup_result,sourcelist[another_index][0])!=-1:
                    popone=backup_result.pop(find_element(backup_result,sourcelist[another_index][0]))
                    find_index=find_element(sourcelist,popone[0])
                    sourcelist[find_index][1]-=1
                    find_index2=find_element(sourcelist,popone[1])
                    sourcelist[find_index2][1]-=1
                sourcelist[another_index][1]=0
        sourcelist.sort(key=takeSecond)  #刷新分数排行榜
            
#print("Final Result:",final_result)
print(len(final_result))

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