描述
题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
数据范围：?1 \le n \le 100 \1≤n≤100??，输入的数据大小满足?2 \le val \le 30000 \2≤val≤30000?
输入描述：
输入说明
1?输入一个正偶数 n
2?输入 n 个整数输出描述：
求得的“最佳方案”组成“素数伴侣”的对数。
示例1
输入：
4 2 5 6 13复制输出：
2复制
示例2
输入：
2 3 6复制输出：
0
思路：
首先将输入的整数分为奇数和偶数分别存入两个列表，因为素数肯定是奇数加偶数才有可能。然后这两个列表就可以看成典型的匈牙利问题求解。遍历偶数，为每个偶数寻找奇数，当奇数偶数之和为素数且此奇数在此轮没有没选过（is_secelt[i] == 0）时，判断此奇数没有被其它偶数选择过(fi_secelt[i] == 0)，或选择过的那个偶数有别的奇数选择（这里就是把这个偶数再寻找一遍奇数看返回是否为真），若为真则返回True，并将记录中的奇数是否被选择的列表相应项记为对应偶数(fi_secelt[i] == o)。注意在为每个偶数寻找奇数时都要初始化is_select列表。
代码：
n = int(input())
m = list(map(int,input().split()))
result = 0
odd = []
even = []
def is_pri(s): #从2遍历到他的平方加一就好，节约时间
for i in range(2,int(s**0.5)+1):
if s%i == 0:
return False
return True
def find_num(even,is_select,fi_select,o): #寻找奇数
for i,e in enumerate(even):
if is_pri(e+o) and is_select[i] == 0:
is_select[i] = 1
if fi_select[i] == 0 or find_num(even,is_select,fi_select,fi_select[i]): # 判断第i位奇数是否被匹配或其匹配到的偶数是否有其他选择
fi_select[i] = o
return True
return False
for i in range(n): #将输入的数分奇数和偶数存储，只有一个奇数加一个偶数的结果才可能是素数
if m[i]%2 == 0:
odd.append(m[i])
else:
even.append(m[i])
fi_select = [0 for i in range(len(even))] #总的
for k in range(len(odd)): #遍历偶数
is_select = [0 for i in range(len(even))] #每一轮的
if find_num(even, is_select, fi_select, odd[k]):
result = result + 1
print(result)?
