华为OD机考2025B卷 - 素数伴侣（Java & Python& JS & C++ & C ）_素数伴侣 python

最新华为OD机试

真题目录：点击查看目录
华为OD面试真题精选：点击立即查看

2025华为od 机试2025B卷-华为机考OD2025年B卷

题目描述

定义两个正整数 a 和 b是“素数伴侣”，当且仅当 a+b 是一个素数。
现在，密码学会邀请你设计一个程序，从给定的 n个正整数 {a1,a2,…,an}中，挑选出最多的“素数伴侣”，你只需要输出挑选出的“素数伴侣”对数。保证 n为偶数，一个数字只能使用一次。

输入描述

第一行输入一个正偶数 n(2≦n≦100)代表数字个数。

第二行输入 n个正整数 a1,a2,…,an(1≦ai≦3×10^4)代表给定的数字。

输出描述

输出一个整数，代表最多可以挑选出的“素数伴侣”的数量。

示例1

输入

42 5 6 13

输出

2

说明

在这个样例中，2 和 5 可以组成一对素数伴侣，6 和 13也可以组成一对素数伴侣。因此，最多可以挑选出 2对素数伴侣。

示例2

输入

41 2 2 2

输出

1

说明

在这个样例中，1 只能使用一次，与任意一个 2组合均是“素数伴侣”。

解题思路

1. 问题分析

• 我们需要从n个数字中选出尽可能多的数字对，使得每对数字的和是素数
• 每个数字只能使用一次
• n是偶数

2. 关键观察

• 奇偶性质：两个数的和为素数（>2），当且仅当一个是奇数，一个是偶数（因为两个奇数相加是偶数，两个偶数相加也是偶数，而大于2的偶数都不是素数）
• 这让我们可以将问题建模为二分图匹配问题：
  • 左侧节点：所有奇数
  • 右侧节点：所有偶数
  • 连接边：当且仅当一个奇数和一个偶数的和是素数时

3. 算法选择

• 这是典型的最大二分图匹配问题，可以使用匈牙利算法（也称为增广路算法）求解
• 匈牙利算法的核心思想是不断寻找增广路径，每找到一条增广路径就能增加一个匹配

4. 算法步骤

1. 将输入数组分成奇数组和偶数组
2. 建立一个match数组记录每个偶数当前匹配的奇数
3. 对每个奇数，尝试为其寻找匹配的偶数：
   • 如果找到一个未匹配的偶数，直接建立匹配
   • 如果找到一个已匹配的偶数，尝试为其当前匹配的奇数重新寻找匹配（递归过程）