HJ28. 素数伴侣
题目描述
给定 n（偶数）个正整数，将它们两两配对，使每一对的和都是素数。求最多能组成多少对。
输入格式
- 第 1 行：n（偶数）
- 第 2 行：n 个正整数
输出格式
- 最多能组成的素数伴侣对数。
示例
示例 1
输入：
4
2 5 6 13
输出：
2
说明：
2+5=7、6+13=19 均为素数，共 2 对。
示例 2
输入：
6
1 2 3 4 5 6
输出：
3
解题思路
第一步：理解问题本质
两两配对使每对和为素数，求最多对数。直接枚举配对方式是排列级别的复杂度，不可行。
第二步：暴力解法（枚举排列）
枚举所有数的排列，每两个一组判断和是否为素数，取最大对数。
问题：n 个数排列为 n! 种，指数爆炸。
第三步：关键观察（奇偶分组）
除 2 以外的素数都是奇数，而两数之和要为素数（必为奇数），必须一个偶数、一个奇数：
- 偶 + 偶 = 偶（≥4），非素数；
- 奇 + 奇 = 偶，非素数（除 2 外）；
- 偶 + 奇 = 奇，可能为素数。
因此把偶数、奇数分成两组，偶数只能与奇数配对，问题转化为二分图最大匹配。
第四步：最优解法（匈牙利算法）
构建二分图：偶数集合与奇数集合，若某偶数 + 某奇数为素数则连边。求二分图最大匹配即最多配对数。
用匈牙利（Kuhn）算法：对每个偶数做 DFS 增广，寻找可匹配的奇数。若当前奇数已被匹配，则尝试递归地为该奇数原来的偶数寻找新的匹配，从而"让位"。
def dfs(ei: int, seen) -> bool:
"""尝试为第 ei 个偶数寻找匹配的奇数"""
for oi, o in enumerate(odds):
if not seen[oi] and is_prime(evens[ei] + o):
seen[oi] = True
if match_odd[oi] == -1 or dfs(match_odd[oi], seen):
match_odd[oi] = ei
return True
return False
完整代码实现
算法可视化 · 逐帧回放这道题的代码68 帧 · 录制输入
import sys
def is_prime(x: int) -> bool:
"""判断是否为素数"""
if x < 2:
return False
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
return False
return True
def solve() -> None:
"""主求解函数"""
data = sys.stdin.buffer.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
evens = [x for x in nums if x % 2 == 0]
odds = [x for x in nums if x % 2 == 1]
# 匈牙利算法：match_odd[oi] 记录当前与第 oi 个奇数配对的偶数下标（-1 表示未配对）
match_odd = [-1] * len(odds)
def dfs(ei: int, seen) -> bool:
"""尝试为第 ei 个偶数寻找匹配的奇数"""
for oi, o in enumerate(odds):
if not seen[oi] and is_prime(evens[ei] + o):
seen[oi] = True
if match_odd[oi] == -1 or dfs(match_odd[oi], seen):
match_odd[oi] = ei
return True
return False
ans = 0
for ei in range(len(evens)):
seen = [False] * len(odds)
if dfs(ei, seen):
ans += 1
print(ans)
if __name__ == "__main__":
solve()
示例推演
以示例 1 2 5 6 13 为例：
- 偶数：
[2, 6]，奇数：[5, 13] - 连边判断：
2+5=7素数 → 连边2+13=15非素数 → 不连边6+5=11素数 → 连边6+13=19素数 → 连边
二分图：偶 2 连奇 5；偶 6 连奇 5、奇 13。
匈牙利过程：
- 为偶 2 匹配：遍历奇数，5 未匹配且 2+5=7 为素数，匹配 2→5。
match_odd[5]=2，ans=1。 - 为偶 6 匹配：遍历奇数，5 已被匹配（属于偶 2），递归尝试为偶 2 找新匹配。偶 2 除 5 外无其他可匹配奇数，无法让位。继续看奇 13，未匹配且 6+13=19 为素数，匹配 6→13。ans=2。
结果： 2。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举排列 | O(n!) | O(n) | 指数级，不可行 |
| 匈牙利算法 | O(E·V) | O(V) | E 为边数，V 为顶点数 |
E 为偶奇素数边数，V 为节点数
易错点总结
1. 忘记奇偶分组
没有利用"素数必为奇数"这一性质做奇偶分组，直接对所有数配对会错过最优解。
2. 素数判断边界
1 不是素数，is_prime 要排除 x < 2 的情况。
3. 匈牙利递归让位
当前奇数已被占用时，必须递归尝试让已匹配的偶数寻找新匹配，不能直接放弃。
4. n 为偶数
题目保证 n 为偶数，但仍要注意最多配对数不超过 min(偶数个数, 奇数个数)。
扩展思考
- 匈牙利算法是求解二分图最大匹配的经典算法，核心是 DFS 增广 + 递归让位。
- 本题的关键是识别出"奇偶分组"这一二分图建模，类似的问题（配对、覆盖、互斥）都可尝试转化为二分图匹配。