题目描述?
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。
输出:
输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入描述:
输入说明
1?输入一个正偶数n
2?输入n个整数
注意：数据可能有多组
输出描述:
求得的“最佳方案”组成“素数伴侣”的对数。
示例1
输入
4
2 5 6 13
2
3 6
输出
2
0实现?
# 判断是否为素数
def is_prime(number):
? ? for i in range(2, number):
? ? ? ? if number % i == 0:
? ? ? ? ? ? return False
? ? return True
# 素数一定为奇数，将number分成奇偶两个列表
def odd_even():
? ? odd = []
? ? even = []
? ? for i in numbers:
? ? ? ? if i % 2 == 1:
? ? ? ? ? ? odd.append(int(i))
? ? ? ? else:
? ? ? ? ? ? even.append(int(i))
? ? return odd, even
# 判断是否可以配对,记录为字典{odd(index:[even[index]])}
def group_prime():
? ? primes = {}
? ? for i in range(len(odd)):
? ? ? ? primes[i] = []
? ? for index_i, i in enumerate(odd):
? ? ? ? for index_j, j in enumerate(even):
? ? ? ? ? ? if is_prime(i + j):
? ? ? ? ? ? ? ? primes[index_i].append(index_j)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? primes[index_i].append(-1)
? ? return primes
# 匹配最佳配对方案
def mate(odd_key):
? ? for index, i in enumerate(even):
? ? ? ? if primes[odd_key][index] != -1 and used[index] == 0:
? ? ? ? ? ? used[index] = 1
? ? ? ? ? ? if companion[index] == -1 or mate(companion[index]) != 0: # 已配对的伴侣是可以重新选择伴侣
? ? ? ? ? ? ? ? companion[index] = odd_key
? ? ? ? ? ? ? ? return 1
? ? return 0
while 1:
? ? try:
? ? ? ? n = int(input())
? ? ? ? numbers = list(map(int, input().strip().split()))
? ? ? ? odd, even = odd_even()
? ? ? ? primes = group_prime()
? ? ? ? new = []
? ? ? ? companion= [-1 for i in range(len(even))] ?# 已配对的素数伴侣
? ? ? ? count = 0
? ? ? ? for k, v in primes.items():
? ? ? ? ? ? used = [0 for i in range(len(even))] ?# 是否已被配对
? ? ? ? ? ? if mate(k):
? ? ? ? ? ? ? ? count += 1
? ? ? ? print(count)
? ? except:
? ? ? ? break