第一次看到 P8795《选素数》这个题，我不由自主地先去找素数判断模板——结果发现这是 2022 年蓝桥杯国赛 A 组的第一道编程题，难度定位在“普及+”，考的根本不是判断素数，而是质因数分解、反向推导，外加一个让不少人误会的差分数组标签。整道题像一记组合拳：题目短，代码不长，但每一步都有思维拐点。如果你是奔着蓝桥杯拿奖去的，或者想练一练数论题里“从结果倒推过程”的套路，这篇内容值得花几分钟看完。
1. 先理解题目：选素数的操作规则到底是什么
1.1 题面还原与示例
这道题原文描述比较绕，我用自己习惯的方式给大家复述一下：给定一个正整数 n，小蓝可以选一个初始整数 x，范围是 2 ≤ x < n。选定之后，小乔开始操作，每一步操作为：取当前数字的一个质因数 p，让当前数字变成 当前数字 + p。小乔的目标是，通过不超过两次操作，把数字恰好变成 n。题目问：有多少个不同的 x，能让小乔完成这个目标。
举个例子。n = 20 时，符合条件的一共有 5 个 x，分别是 10、12、15、16、18。比如 x = 16 时，16 的质因数是 2，加一次到 18；18 的质因数是 2 和 3，再取 2，加到 20，两步完成。如果你把 x 选成 11，11 是质数，一次操作只能到 22，无论如何都不可能变成 20，所以 11 就不符合条件。
这里有个特别容易看错的地方：每一步可以用的质因数，必须是“当前数字”的质因数，不是 n 的质因数，也不是随便一个质数。这个限制直接决定了操作路径的形状。
1.2 正向模拟为什么走不通
第一反应肯定是暴力模拟：枚举所有可能的 x，然后从 x 开始尝试所有质因数组合，看能不能在两步之内碰到 n。问题是这个搜索空间会迅速膨胀。x = 2 时，唯一质因数是 2，下一步是 4；4 的质因数是 2，下一步是 6；6 的质因数有 2 和 3，下一步可能是 8 或 9；再往后每个数都可能分叉出两三个方向。如果 x 是 12，质因数有 2 和 3，一次操作已经能走到 14 或 15。
暴力枚举 x 再加上分支搜索，复杂度大概是 O(n × 质因数个数^2)，n 稍微大一点，比如 10^6 甚至 10^7，直接超时。更关键的是，这种正向枚举大量路径里，绝大多数都走不到 n，纯属浪费。
1.3 终点只有一个：反向思考直接化简问题
竞赛里处理这种“从某个起点出发，按照规则走到固定终点”的问题，第一优先级永远是反向考虑。为什么？因为起点有 n 个候选，但终点只有一个 n。
把操作过程倒过来看：如果一次操作能把 x 变成 n，说明存在一个质数 p，满足 x + p = n，并且 p 是 x 的质因数。那么反向就是：站在 n 这里，往前退一步，退到的位置是 n - p。
这里有个非常漂亮的结论：如果 p 是 x 的质因数，又满足 x = n - p，那么 p 同时也能整除 n。因为 n = x + p，两项都是 p 的倍数。换句话说，一次操作可达的 x，一定等于 n 减去 n 的某个质因数。于是，“一步可达”的问题就变成了“枚举 n 的所有质因数”。
两步操作同样可以反向拆解：第一次从 x 到某个中间数 y，第二次从 y 到 n。反向来看，最后一步必须从 n 减去 n 的一个质因数，得到 y；再往前一步，必须从 y 减去 y 的一个质因数，得到 x。所以 x = n - p - q，其中 p 是 n 的质因数，q 是 n - p 的质因数。
这一下子就把一个图搜索问题，变成了一个枚举组合问题。
2. 一步两步可达条件：把搜索变成质因子组合
2.1 一步可达：p 必须是 n 的质因数
先严格推一遍一步条件。假设从 x 开始，选一个质因数 p，加一次到 n：
n = x + p
因为 p 是 x 的质因数，所以 x ≡ 0 (mod p)，于是 n ≡ p ≡ 0 (mod p)，所以 p 整除 n。
反过来说，如果 p 是 n 的一个质因数，令 x = n - p，那么 x 一定是 p 的倍数，p 确实是 x 的质因数。于是从 x 出发选 p，一步就能到 n。
所以一步可达的候选集合就是：
{p 是 n 的质因数} → x = n - p
需要注意 x 的范围：要求 2 ≤ x < n。如果 n 本身是素数，比如 n = 7，唯一质因数是 7，x = 0，直接越界，一步可达的 x 一个都没有。
2.2 两步可达：连续做两次“倒推质因数减法”
两步的推导同样严格。设第一次操作加的质因数是 q，得到中间数 y；第二次操作加的质因数是 p，得到 n。
n = y + p，p 是 y 的质因数 → p 整除 y，又因为 y = n - p，两边都是余数关系，可以得到 p 整除 n。
这说明最后一步用的 p，仍然必须是 n 的质因数。这和一步的结论一致，因为最后一步是从 y 到 n，y 类似上文的 x。
再看中间一步：y = x + q，q 是 x 的质因数，所以 q 整除 x，于是 q 整除 y。也就是说，q 必须是 y = n - p 的质因数。
于是两步可达的完整条件：
- 枚举 n 的每个质因数 p，令 y = n - p；
- 再枚举 y 的每个质因数 q；
- x = y - q = n - p - q；
- 检查 x 是否满足 2 ≤ x < n，满足则计入答案。
到达同一个 x 可能有多条路径，比如 n = 20 时，n - p 的路径里 p = 2 得到 y = 18，q = 3 得到 x = 15；另一条路径 p = 5 得到 y = 15，q = 5 得到 x = 10。不冲突。但也有重复情况，这一步放到后面边界章节细说。
2.3 用 n = 20 手动推导全过程
用 n = 20 完整走一遍，能直观看到整个过程：
n = 20 分解质因数：20 = 2^2 × 5，得到 p 的集合 {2, 5}。
一步可达：
- p = 2，x = 20 - 2 = 18；
- p = 5，x = 20 - 5 = 15。
两步可达：
- p = 2，y = 18，分解 18 = 2 × 3^2，质因数集合 {2, 3}：
- q = 2，x = 18 - 2 = 16；
- q = 3，x = 18 - 3 = 15。
- p = 5，y = 15，分解 15 = 3 × 5，质因数集合 {3, 5}：
- q = 3，x = 15 - 3 = 12；
- q = 5，x = 15 - 5 = 10。
合并去重后得到 {18, 15, 16, 12, 10}，正好 5 个。和题目样例完全吻合。
2.4 质因数个数的上界：为什么组合枚举可行
有人会担心：如果 n 很大，质因数组合会不会爆炸？实际完全不用担心。一个正整数 n 的不同质因数个数非常有限。以 10^6 为例：
2 × 3 × 5 × 7 × 11 × 13 × 17 = 510510，再乘一个 19 就超过 10^6 了。也就是说，10^6 以内的数最多只有 7 个不同质因数。
到了 10^9 级别，最多也就 9 个不同质因数。每一步要枚举的 p 最多十几个，对每个 p 得到的 y 再分解一次，q 的个数同样是个位数。组合数撑死也就一百左右。这就是为什么这道题能靠“枚举质因数”直接碾过去，而不是做搜索。
3. 质因数分解的正确打开方式
3.1 场景分析：哪些数需要分解
按照上面的推导，我们需要分解的对象包括：
- n 本身：求出所有质因数，用来找一步可达点和两步的中间数 y；
- 每个 y = n - p：求出所有质因数，用来找两步可达点。
这些数字的个数很少，理论上用最暴力的试除法，对每个数从 2 试到 sqrt(x)，就能在 O(sqrt(n)) 的时间内完成分解。比如 n = 10^6，sqrt(n) 只有 1000，完全够用。那为什么竞赛里更推荐线性筛预处理？因为实际赛场上你不可能只写这一道题，线性筛 spf 数组是数论题的万能底座，写一次能顺手解决很多问题。更重要的是，如果题目数据范围到 10^7，试除法虽然也能过，但每次都从头试除，常数和代码量都不太优雅。
3.2 方法一：试除法
最朴素的分解方式，适合小数据验证和快速理解原理。
vector<int> factorByTrial(int x) { vector<int> res; for (int i = 2; 1LL * i * i <= x; ++i) { if (x % i == 0) { res.push_back(i); while (x % i == 0) x /= i; } } if (x > 1) res.push_back(x); return res; }注意最后一步：如果 x 没有被除尽，剩余部分一定是大于 sqrt(原x) 的一个质数，必须单独加进去。这个细节很多人会漏。
3.3 方法二：线性筛 spf 预处理
spf 全称 smallest prime factor，意思是“最小质因子”。预处理出每个数的最小质因子后，分解任意一个数就变成了一个简单的 while 循环：每次除以当前数的最小质因子，并记录当前最小质因子为 p，然后不断去掉 x 中所有的 p。
线性筛的模板：
vector<int> spf; void eulerSieve(int n) { spf.assign(n + 1, 0); vector<int> primes; for (int i = 2; i <= n; ++i) { if (spf[i] == 0) { spf[i] = i; primes.push_back(i); } for (int p : primes) { long long v = 1LL * i * p; if (v > n) break; spf[v] = p; if (i % p == 0) break; // 保证每个合数只被最小质因子筛一次 } } } vector<int> factorBySpf(int x) { vector<int> res; while (x > 1) { int p = spf[x]; res.push_back(p); while (x % p == 0) x /= p; } return res; }记忆线性筛的关键就一行：if (i % p == 0) break;。它的作用是让每个合数只被它的最小质因子筛掉一次。很多初学者在这里直接抄模板，但从没理解过，一旦题目变化就露馅。你可以试着把 n = 12 跑一遍，观察 12 为什么只会被 2 筛到，而不会被 3 筛到。
3.4 如何扩展到超大 n：Pollard-Rho 思路
如果 n 是 10^12 甚至 10^18 级别，不管试除法还是线性筛都无法直接预处理。这时候需要 Miller-Rabin 素数判定 + Pollard-Rho 大数分解。核心思想是：Miller-Rabin 高速判断一个数是不是素数，Pollard-Rho 随机找到一个因子，然后递归分解。
由于蓝桥杯本科组基本不会出到这个量级，我在这里只提思路，不展开完整实现。真正要记住的是：不管用什么方法，最终输出的都是“不重复质因子集合”，后续枚举逻辑完全一样。这也说明，选素数这道题真正的难点从来不是质因数分解本身，而是你能不能想到“反向枚举质因子”这个关键一步。
3.5 分解结果的存储与去重
用 spf 分解出的质因子可能包含重复项，但是我们的推导中“每个不同质因数”只影响一条路径。同一个数 12 分解出的质因数集合是 {2, 3}，不用关心 2 出现了几次。所以 factorBySpf 里用 while 循环一次性除干净，保证 res 里每个质数只出现一次。这个去重是组合枚举的关键，如果不去重，n = 8 时会多算一步路径，导致结果偏大。
4. 差分数组在本题的定位：从“标记可达点”到“区间统计”
4.1 为什么我的解法不需要显式差分
如果你在网上搜题解，会看到不少文章标题写着“质因数分解 + 差分数组”。这里必须给大家泼一盆冷水：这题求的是“符合条件 x 的总数”，我的做法里完全没有用到差分数组，也不需要用。差分数组本质上是处理“区间批量加、最后单点查询”的工具，而本题的可达点集合是一个个离散的点，不是连续区间。
那标签里的“差分数组”从哪来？我猜测有两种可能。第一种：部分选手在统计答案时，用 frequency 数组标记所有可达点，然后做一次前缀和，这正好是差分的“逆过程”——先构建频次数组，再用前缀和还原出每个点是否可达。第二种：本题的某个变体或同类题目会把 n 的范围换成区间 [L, R]，让你统计区间内有多少个 x，这时候差分数组就能派上用场。
4.2 如果题目变成区间查询，差分/前缀和的用法
假设题目变成：给定 m 次询问，每次给一个区间 [L, R]，问区间内有多少个 x 是可达的。最自然的做法是把可达点集合存下来排序，然后二分查位置。但这道题如果用差分数组思想，可以更直接：维护一个长度为 n 的数组 freq，对于每个可达点 x，执行 freq[x] = 1，最后对 freq 做前缀和。这样任意 [L, R] 的答案就是 freq[R] - freq[L - 1]。
如果原来的“点标记”变成“区间标记”，比如某种操作能一次性覆盖 [a, b] 内所有数，那么差分数组的优势才真正体现：对每个区间，只需要在 diff[a] 加 1，diff[b + 1] 减 1，最后一次性前缀和还原，就把 O(区间长度) 的区间加变成了 O(1) 的端点操作。这是差分数组最核心的用法。
实际赛场上，见到标签里有“差分数组”，先看看题目要你输出什么：如果只是输出总数，多半不需要差分；如果是区间统计、区间覆盖、多次查询，再考虑差分。
4.3 完整 C++ 实现
下面给出这道题我认为最清晰的完整代码，使用线性筛 spf + 反向枚举质因子 + 去重集合：
#include <bits/stdc++.h> using namespace std; vector<int> spf; void eulerSieve(int n) { spf.assign(n + 1, 0); vector<int> primes; for (int i = 2; i <= n; ++i) { if (spf[i] == 0) { spf[i] = i; primes.push_back(i); } for (int p : primes) { long long v = 1LL * i * p; if (v > n) break; spf[v] = p; if (i % p == 0) break; } } } vector<int> factorDistinct(int x) { vector<int> res; while (x > 1) { int p = spf[x]; res.push_back(p); while (x % p == 0) x /= p; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; eulerSieve(n); vector<bool> ok(n + 1, false); vector<int> candidates; auto addCandidate = [&](int x) { if (x >= 2 && x < n && !ok[x]) { ok[x] = true; candidates.push_back(x); } }; vector<int> facN = factorDistinct(n); for (int p : facN) { addCandidate(n - p); } for (int p : facN) { int y = n - p; if (y < 2) continue; vector<int> facY = factorDistinct(y); for (int q : facY) { addCandidate(y - q); } } cout << candidates.size() << '\n'; return 0; }代码本身不长，只有四十多行。核心就两点：一是 factorDistinct 一定要返回“去重后的质因数集合”，二是 addCandidate 里的边界检查 x ≥ 2 且 x < n，缺一不可。
4.4 复杂度分析
线性筛预处理 spf 的复杂度是 O(n)。之后对 n 和每个 n - p 做分解，每次分解消耗 O(质因数个数 × 平均幂次)，可以近似看作 O(logn)，因为质因数个数非常有限。总时间复杂度 O(n + 质因数组合枚举)，空间复杂度 O(n)。
如果 n 给到 10^6，这个解法在评测机上跑起来基本是 0 秒级。如果给到 10^7，线性筛内存大约是 40MB，也还能接受。要是 n 更大，就需要换用 3.4 节提到的 Pollard-Rho 方案，把筛法去掉，内存直接降到 O(1)。
5. 蓝桥杯实战中的边界条件与避坑清单
5.1 x = 1、x = n 等边界的处理
题目要求初始 x 必须满足 2 ≤ x < n，所以两个边界都不能漏。x = 1 的情况下，1 没有质因数，任何操作都做不了，必须排除。x = n 的情况下，不需要操作就已经在终点，题目限定了 x < n，也必须排除。
为什么不把 x = n 加进答案？因为如果允许，答案永远至少是 1，题目失去了区分度。从这个细节可以看出，出题人在设计数据时是有意考察选手对题目描述的精细理解。我在第一版代码里就漏了 x < n 这个条件，结果样例 n = 20 输出变成了 6，多算了一个 20，排查了半天才发现是边界问题。
5.2 重复到达同一个 x 的去重问题
前面提到，同一个 x 可能通过不同的质因数组合被多次访问到。比如 n = 20 时，15 既可以从 n - 5 一步到达，也可以从 n - 2 - 3 两步到达。如果只统计不检查重复，直接对每个组合 push_back，答案会偏大。
常规做法是开一个 visited 布尔数组，标记过就不再加入候选集合。在最终统计时，直接输出 visited 数组中被标记的数量即可。不要把去重留到最后排序再加，那样代码会多绕一步。
5.3 质因数组合顺序去重问题
有人会问：枚举 p 和 q 时，如果先 p 后 q 和先 q 后 p 得到同一个 x，怎么办？实际上这个担心是多余的。倒推过程中，最后一步加的必须是 n 的质因数，这一步是固定的；第一步加的是中间数的质因数。顺序已经被“最后一步”锁定，不会出现同一组合反序枚举的情况。
但是要注意一种特殊情况：当 n - p 的质因数 q 恰好也等于 n 的某个质因数时，可能出现两个不同 p 值的路径计算出同一个 x。这正是 5.2 节去重要解决的问题，和顺序无关。
5.4 复杂度估计与数据范围选型
蓝桥杯这类题的时间限制通常是 1 秒到 3 秒。如果是 O(n) 的线性筛，n = 10^6 轻松过，n = 10^7 时要注意数组内存和常数优化，建议把 spf 从 int 改成更紧凑的类型，或者改用试除法。如果是试除法只分解少量数字，n 到 10^9 也能过，因为需要分解的数字数量实在太小，每次 sqrt(n) 大约三万多次运算，完全不在话下。
判断数据范围的一个经验法则：看到 n ≤ 10^6，优先线性筛；n ≤ 10^9，试除法优先；n ≥ 10^12，Pollard-Rho 起步。这道题标题写的是“普及+”，数据范围大概率不会超过 10^6，线性筛足够。
5.5 这类数论题的通用套路总结
最后说说我从这道题里提炼出的通用套路，对蓝桥杯其他数论题同样适用。
第一，看到“从若干起点出发，经过某种操作到达固定终点”的问题，优先反向思考。终点只有一个，起点有 n 个，反向之后枚举量急剧下降。
第二，质因数个数是 O(log n) 级别的，枚举质因子组合通常不会超时。很多看起来像搜索的题，本质是枚举质因子。
第三，如果题目涉及区间统计、区间覆盖，先用差分数组把区间加减转化为端点操作，最后一次性前缀和还原。这是数论题和数据结构题的常见结合点。
第四，代码实现上，把“边界检查”单独抽成一个函数，所有候选点都走同一个入口，能有效避免重复代码导致的漏判。
按照这个思维框架去刷题，你会发现“选素数”这道题根本不是难题，它考察的只是你能不能在最开始那一步转过弯来。
