本文主要是介绍华为机考入门python3--（28）牛客28-素数伴侣，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分类：质数、素数、贪心算法、矩阵
知识点：
-
素数里除了2，都是奇数
-
奇+奇=偶，偶＋偶=偶
-
对矩阵求和 sum(map(sum, matrix))
-
查找元素 3 在列表中的索引 my_list.index(3)
题目来自【牛客】
质数又称素数，是指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数。例如，2、3、5、7、11等都是质数。
1. 素数里除了2，都是奇数。奇+奇=偶，偶＋偶=偶，大于2的偶数都不是素数。所以素数伴侣一定是由一个偶数一个奇数组成。
2. 把数组中的奇数和偶数分开保存，建立二维数组的交叉表格，判断各个组合是否能构成素数
3. 遍历二维数组的每行，也就是偶数，利用贪心算法，每次把成功配对次数最少的那个偶数和第一个与之配对的奇数从数组里删除，直到二维数组里不存在配对的奇偶数对。
（来自牛客id：399316398的用户)
# 质数又称素数，是指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数。
# 例如，2、3、5、7、11等都是质数。
def isPrime(num):# 素数是一个大于1的自然数if num < 2:return False# 能不能被其它数整除# a ** b 表示a的b次方。for i in range(2, int(num ** 0.5) + 1):if num % i == 0:return Falsereturn Truedef find_prime_pairs(nums):# 把数组中的奇数和偶数分开保存even, odd = [], []for i in nums:if i % 2 == 0:even.append(i)else:odd.append(i)# 找出所有可能的素数组合# 都是偶数或者都是奇数if not (even and odd):return 0else:# 建立二维数组的交叉表格，判断各个组合是否能构成素数matrix = []# 行是偶数for r in range(len(even)): # Iterating over the rows of the output matrixrow = [] # Creating an empty list to store the row elements# 列是奇数for c in range(len(odd)): # Iterating over the columns of the output matrixif isPrime(even[r] + odd[c]): # Checking if the sum of the elements from even and odd meets the prime conditionrow.append(1) # If the sum is prime, adding 1 to the row listelse:row.append(0) # If the sum is not prime, adding 0 to the row listmatrix.append(row) # Adding the constructed row to the output matrix# print(matrix)# 素数伴侣的组数cnt = 0# 贪心算法（删除最小匹配的行）# map(sum, matrix)的意思是，对matrix中的每一行（即每一个子列表）应用sum`函数，计算每一行的和# 如果二维矩阵中还有1while sum(map(sum, matrix)):# k = [float("inf"), 0] 可以被解释为：一个列表，其中第一个元素是正无穷大，第二个元素是0# k中的第一个元素表示一行中的总和，代表可以该偶数可以和所有奇数产生多少个素数伴侣，第二个元素表示行号k = [float("inf"), 0]# 求和最小的行for r in range(len(matrix)):if 0 < sum(matrix[r]) < k[0]:k = [sum(matrix[r]), r]# 每次把成功配对次数最少的那个偶数和第一个与之配对的奇数从数组里删除r, c = k[1], matrix[k[1]].index(1)even.pop(r)odd.pop(c)matrix.pop(r)for i in matrix:# 每行中删除第c个元素i.pop(c)cnt += 1return cntn = int(input())
numbers = list(map(int, input().split()))
# print(numbers)
print(find_prime_pairs(numbers))
by 软件工程小施同学
这篇关于华为机考入门python3--（28）牛客28-素数伴侣的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
