PRIME / LAB 返回埃氏筛实验室

PRIME PARTNER · HJ28 · FROM GREEDY TO AUGMENTING PATH

素数伴侣题解

把 n 个正整数配成最多对“和为素数”的伴侣。先尝试贪心，发现它会被顺序卡住； 再观察奇偶结构得到二分图，最后用增广路让配对学会“让位”。

题目→奇偶分组→贪心反例→ 增广路→最大匹配

01 · 题目

题目：素数伴侣

本章作用建立问题模型：把“配对”转成“边选择”，明确目标是最多的一对一组合。
主线知识

题目约束、伴侣定义、输出目标。

扩展知识

本题出自牛客 HJ28，是华为机试经典题。

题目描述

定义两个正整数 a、b 是“素数伴侣”，当且仅当 a + b 是一个素数。现在从给定的 n 个正整数中挑选出最多的素数伴侣，输出最多能组成的对数。保证 n 为偶数，一个数字只能使用一次。

输入输出与数据范围

项目说明
输入第一行正偶数 n（2 ≤ n ≤ 100）；第二行 n 个正整数 a_i（1 ≤ a_i ≤ 3×10⁴）
输出一个整数，最多可以挑选出的素数伴侣对数
关键约束每个数字只能使用一次，配对总数不超过 n/2
问题形态 一次配对占用两个数字，目标是最多的一对一组合。

候选数字分成两类角色时，这就是标准的二分图最大匹配；判断“能不能配”需要素数表，正好接续埃氏筛实验室。

剩余问题需要先找出“哪些数字之间可以配对”，再选择最多互不冲突的配对。

02 · 特殊结构

为什么是二分图

本章作用用素数的奇偶性证明：所有合法边都只跨奇偶两组，问题天然是二分图匹配。
主线知识

素数只有 2 是偶数；奇偶性决定边的分组。

扩展知识

1 + 1 = 2 的理论边界，牛客测试数据不卡。

素数与奇偶性

性质：大于 2 的素数都是奇数；素数里唯一的偶数是 2。

推论：两个不同正整数 a、b 满足 a + b 是素数时，除了 1 + 1 = 2 这个唯一例外，a 和 b 必然一奇一偶——同奇或同偶的和都是偶数，而不等于 2 的偶数不可能是素数。

这个性质把 n 个数字分成两组：偶数一组、奇数一组。所有合法边都只跨组连接，组内无边，这就是二分图。

左部偶数

a_i % 2 == 0

每条边都满足 和为素数
右部奇数

a_i % 2 == 1

建图：偶数 → 奇数

先筛出范围内所有素数（最大和不超过 max(nums)×2），再对每个偶数、每个奇数检查 a + b 是否为素数：是则连边。每条边代表“这两个数字可以组成一对素数伴侣”。

边只建一个方向（偶数 → 奇数）就够了：匹配是从左部发起搜索，右部用占用记录回答，双向边只会造成重复。

结果问题变成：在二分图中选择尽量多的边，任意两条边不共享端点——最大匹配。

03 · 贪心失败

贪心为什么不够

本章作用先执行“先到先得”的贪心，用反例证明它可能停在非最优答案。
主线知识

贪心只找空闲右点，不会撤销旧配对。

扩展知识

反例来自“早期选择占用了后来更稀缺的资源”。

反例：2, 3, 4, 5

输入 2、3、4、5。检查所有和为素数的组合：2+3=5、2+5=7、3+4=7 是素数，其余不是。 合法边为：2—3、2—5、3—4。

贪心过程：按顺序先处理偶数 2，2 先匹配 3；轮到偶数 4 时，4 唯一能配的 3 已被占用，只能放弃——得到 1 对。

实际最优：2 配 5、4 配 3——得到 2 对。

贪心结果1

2—3；4 无可用岗位

早期选择占用了
后来者唯一的出路
最优结果2

2—5、4—3

贪心的结构缺陷

痛点证据 贪心只寻找空岗位，永远不会修正旧决定。

如果 2 当初选的是 5 而不是 3，4 就能配 3。贪心缺少“让 2 换一个岗位”的机制，因此可能停在局部最优。

剩余问题需要一种允许调整已有配对、又不重新枚举全部方案的方法——增广路。

04 · 让位机制

匈牙利算法：让位机制

本章作用用最小例子展示“请原搭档另找”的让位链，说明它如何把匹配数加一。
主线知识

递归让位、交替路、增广路、翻转。

扩展知识

Berge 定理：没有增广路时匹配最大。

让位例子：A 与 B

两个人抢岗位：A 能去岗位 1、2，B 只能去岗位 1。贪心会得到 A—1、B 失败；匈牙利让 B 先试岗位 1，发现被 A 占用后，递归请 A 另找——A 换到岗位 2，B 接管岗位 1，最终两对都配成。

1
B → 岗位 1

走一条未选择的边，发现岗位 1 已被 A 占用。

2
岗位 1 → A

沿当前匹配边找到原搭档 A。

3
A → 岗位 2

A 尝试其他出路，岗位 2 空闲，让位成功。

4
翻转

B—1、A—2 同时成立，匹配数从 1 变 2。

交替路与增广路

交替路

相邻两条边一条属于当前匹配、一条不属于，不能连续两条同类边。路径本身不要求端点自由。

增广路
  1. 本身是一条交替路。
  2. 两个端点都是未匹配点。
  3. 因此非匹配边比匹配边多一条。

翻转增广路：删旧匹配边、加新非匹配边，匹配数严格 +1。

统一视角：直接匹配也是一条增广路

“直接匹配成功”并不是另一种方式，它本身就是一条长度最短的增广路：起点是自由点、终点是空闲岗位、路径只有一条非匹配边（非匹配边比匹配边多一条：1 > 0）。

因此代码里的 j not in match 与 try_match(match[j], seen) 是同一个动作的两个分支：前者表示终点已到、递归结束；后者表示终点未到、继续沿匹配边延伸。所有成功都统一成“找到一条增广路并翻转”，递归结构因此成立。

结论贪心失败是因为不会让位；增广路正是“让位链”的正式表达。

05 · 详细拆分

seen 的详细拆分

本章作用把 A/B 例子的两轮执行逐步展开，解释 seen 如何防止递归绕圈。
主线知识

每轮新建 seen、链内共享、标记时机在递归之前。

扩展知识

没有 seen 时递归会形成无限环。

第一轮：A 直接占用

调用 try_match(A, set())，传入全新的空集合。

动作seenmatch
A 试岗位 1，1 不在 seen，加入{1}{ }
岗位 1 空闲，直接占用 match[1] = A{1}{1: A}
返回 True{1}{1: A}

第二轮：B 请 A 让位

调用 try_match(B, set())，同样从空集合开始，但递归时传的是同一个 seen。

动作调用栈seenmatch
B 试岗位 1，加入 seentry_match(B){1}{1: A}
岗位 1 被 A 占用 → 递归 try_match(A, 同一个 seen)try_match(B) → try_match(A){1}{1: A}
A 看到岗位 1 已在 seen 中，跳过try_match(B) → try_match(A){1}{1: A}
A 试岗位 2，加入 seentry_match(B) → try_match(A){1, 2}{1: A}
岗位 2 空闲，match[2] = A，返回 Truetry_match(B) → try_match(A){1, 2}{1: A, 2: A}
B 收到 True，match[1] = B，返回 Truetry_match(B){1, 2}{1: B, 2: A}

最终匹配 {1: B, 2: A}，共 2 对。

为什么不会重复找到旧边

关键机制 seen.add(1) 发生在递归之前，递归传同一个 seen。

B 尝试岗位 1 时先把 1 写进清单，A 在递归里第一眼看到岗位 1 就是“已尝试”，直接 continue，只能去找其他出路（岗位 2）。岗位 1 的占用状态在一轮搜索里只被检查一次。

没有 seen 会怎样

A 试岗位 1 → 岗位 1 被 A 占用 → 递归请 A 另找 → A 又试岗位 1 → 又被 A 占用 → 再请 A 另找……递归永远不会停止。seen 就是剪掉这个环的剪刀。

seen 的语义

记录对象

右侧节点（岗位），不是左侧节点。

生命周期

每轮外层调用新建 set()，同一轮递归链共享。

标记时机

在检查占用状态之前 add，防止同一右点被重复检查。

不跨轮共用

下一轮重新尝试所有右点，否则会漏掉合法匹配。

06 · 实现

优雅实现

本章作用把筛法、建图、匈牙利写成一份克制而完整的 Python 代码。
主线知识

筛表、下标分组、字典建图、dict 匹配表、sum 统计。

扩展知识

两个 1 的理论边界不处理也能通过牛客数据。

Python 版

PYTHON素数伴侣 · 匈牙利O(|L|·|E|)
import math

def sieve(limit: int) -> list[bool]:
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(limit) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return is_prime

n = int(input())
nums = list(map(int, input().split()))
is_prime = sieve(max(nums) * 2)

# 用下标分组，避免重复值合并；只建 偶数 -> 奇数 单向图
evens = [i for i, x in enumerate(nums) if x % 2 == 0]
odds  = [i for i, x in enumerate(nums) if x % 2 == 1]
graph = {i: [j for j in odds if is_prime[nums[i] + nums[j]]] for i in evens}

match = {}          # match[奇数下标] = 它当前的偶数搭档

def try_match(i: int, seen: set[int]) -> bool:
    for j in graph[i]:
        if j in seen:
            continue
        seen.add(j)
        if j not in match or try_match(match[j], seen):
            match[j] = i
            return True
    return False

print(sum(try_match(i, set()) for i in evens))

代码阅读要点

graph

字典推导 + 列表推导一行建图，只存偶数→奇数方向。

match

字典表达“奇数当前的偶数搭档”，避免双向数组不同步。

seen

每轮新建 set()，递归链共享，防环。

try_match

岗位空闲直接占；被占用递归请原搭档让位。

sum(...)

对每个偶数尝试一次增广，成功次数即答案。

核心try_match 是找增广路，外层是每个左点试一次增广；组合起来是匈牙利算法，不是贪心。

07 · 复杂度

复杂度与经典 C 版

本章作用说明复杂度来源，并展示竞赛中常用的 C 数组实现。
主线知识

O(|L|·|E|) 的来源与左部选小的优化。

扩展知识

C 版用邻接矩阵与全局数组，逻辑与 Python 版一致。

左部选小的一侧

匈牙利复杂度是 O(|L|·|E|)：外层遍历左部每个点，每个点 DFS 扫描自己的边。 因此把数量较少的一侧当作左部，可以减少外层轮数。n ≤ 100 时收益不明显，但这是竞赛实现里的常见习惯。

C 经典版

C素数伴侣 · 匈牙利邻接矩阵
#include <stdio.h>
#include <string.h>
#include <math.h>

char used[88], match[88][88];
int even[88], idx_e, odd[88], idx_o, cp[88], cnt;
int *small, idx_s, *big, idx_b;

int IsPrime(int num) {
    int i = 2, j = sqrt(num);
    for (; i <= j; i++)
        if (num % i == 0) return 0;
    return 1;
}

int DG(int n) {
    int i;
    for (i = 0; i < idx_b; i++) {
        if (match[n][i] && !used[i]) {
            used[i] = 1;
            if (cp[i] == -1) { cp[i] = n; cnt++; return 1; }
            if (DG(cp[i]))   { cp[i] = n; return 1; }
        }
    }
    return 0;
}

int main(void) {
    int i, j, tmp, num;
    while (scanf("%d", &num) != EOF) {
        idx_o = idx_e = 0;
        for (i = 0; i < num; i++) {
            scanf("%d", &tmp);
            if (tmp & 1) { odd[idx_o++] = tmp; continue; }
            even[idx_e++] = tmp;
        }
        if (idx_o > idx_e) { small = even; idx_s = idx_e; big = odd; idx_b = idx_o; }
        else               { small = odd;  idx_s = idx_o; big = even; idx_b = idx_e; }
        for (i = 0; i < idx_s; i++)
            for (j = 0; j < idx_b; j++)
                match[i][j] = IsPrime(small[i] + big[j]);
        memset(cp, -1, idx_b * sizeof(int));
        for (i = cnt = 0; i < idx_s; i++) {
            memset(used, 0, idx_b * sizeof(char));
            DG(i);
        }
        printf("%d\n", cnt);
    }
    return 0;
}
方案复杂度特点
贪心O(|L|·|E|)可能停在非最优答案
匈牙利（DFS 增广）O(|L|·|E|)允许让位，保证最大匹配
Hopcroft–Karp（进阶）O(|E|·√|V|)大规模稀疏图更快

08 · 参考

继续阅读

← 返回 Blog