【牛客·华为】Python 素数伴侣

87 阅读 0 评论 58 点赞

我是靠谱客的博主稳重鸵鸟，最近开发中收集的这篇文章主要介绍【牛客·华为】Python 素数伴侣，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述

题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如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)