第一次在题库里刷到“质数的后代”这个题名时，我愣了几秒：质数怎么还有后代？点开题面才反应过来，它说的是形如 p×q 的合数，其中 p、q 都是质数。数学上这东西有个正经名字叫半素数，也有人叫二素数。你不需要刻意记这个名词，但心里要清楚：这道题考的核心不是难，而是“质数判定 + 因数拆分 + 预处理”这三件事怎么组合才快。
这篇文章我会从题目本质、设计思路、完整实现、踩坑实录到变体扩展一层层讲透。不管你是刚开始刷算法题的初学者，还是准备比赛想捡起这块知识的选手，看完都能直接照着写，不会再被“后代”这个包装名绕晕。
1. 题目到底在问什么：先把话说明白
1.1 “质数的后代”这个包装名下的数学本质
先下个明确定义：一个合数 n，如果存在两个质数 p、q，使得 n = p × q，那么这个 n 就是“质数的后代”。注意两个关键点，第一，p 和 q 可以相等，所以 4 = 2 × 2、9 = 3 × 3、49 = 7 × 7 都算；第二，p 和 q 都必须是质数，所以 12 = 2 × 6 不算，因为 6 不是质数，而 12 = 3 × 4 也不算，4 同样不是质数。
说得再直白一点，这类合数的因数分解式里，只包含两个质因子，而且允许重复。你可以先做质因数分解，数一数所有质因数的总个数是不是正好 2，这也是后面判断逻辑的另一种等价写法。
这个定义里最容易翻车的点是：1 算不算？答案是不算。因为 1 既不是质数也不是合数，它不可能被写成两个质数的乘积。质数本身算不算？比如 5，它确实能写成 5 = 1 × 5，但 1 不是质数，所以 5 不算“质数的后代”。这些边界值看起来简单，实际代码里却是一等一的坑，我后面专门用一节来讲。
1.2 典型输入输出形态
这类题在不同题库里的输入格式不太一样，但常见的一般是这样：
- 第一行给一个整数 n，表示要判断的数字个数。
- 第二行给 n 个正整数，每个数字不超过某个上限，比如 10^5、10^6 或者更大。
- 输出格式要么是每个数对应一行 YES / NO，要么是输出其中所有“质数的后代”的个数。
有的变体题还会反过来问：给定一个区间 [L, R]，统计这个区间里有多少个数是“质数的后代”。那本质上就是把单个判断变成区间批量统计，你需要再配合前缀和或者离线预处理。
我下面给的实现以“一次性读入所有待判断数字，逐个输出”为准，但核心判断函数是通用的，改一下循环就能适配区间统计版本。
1.3 三个容易踩的定义陷阱
先把这个说透：题目说的“合数为两个素数的乘积”，很多人下意识会去枚举所有质数对 p、q，然后判断 p×q 是不是等于 n。这个思路没错，但直接双重循环枚举质数会非常慢，后面会专门分析。
第二个陷阱是只判断“两个因子都是质数”，却忘了“n 本身必须是合数”。虽然定义里已经说了“合数”，但代码写起来容易漏——如果 n 是质数，你可能会在枚举到 p = 1 时出错。我见过不少初学者写的程序，把 2、3、5 这样的质数也判定为 YES，就是因为没有处理“质数不能拆成两个质数相乘”这一条。
第三个陷阱是把范围搞错。有些人会先把所有质数筛出来，然后对 n 的每个约数 d 判断 d 与 n/d 是否都是质数。这个思路对，但很多人枚举 d 时枚举到了 n 本身，比如 n = 2，直接判断 d = 2 时 n/d = 1，1 不是质数，所以输出 NO，这倒是没错。可一旦数据范围变大，这种“无脑枚举所有约数”的方式就会超时。原因也很简单：约数判断本身没优化，等于变相退化成 O(n) 的试除。
2. 整体设计思路：别一上来就逐个数硬试
2.1 裸试除为什么慢
最朴素的做法，对每个待判断的数 x：
- 从 2 试除到 sqrt(x)，找一个 x 的因子 p。
- 判断 p 和 x/p 是否都为质数。
- 判断质数时又是一个从 2 到 sqrt(p) 的试除。
如果待判断的数有 m 个，每个数最大是 MAX，这么做的最坏复杂度大约 O(m × sqrt(MAX) × sqrt(MAX))，这个数量级在 MAX 达到 10^6、m 达到 10^5 时完全跑不动。
这里的关键认知是：我们面对的是“一批数”，不是单独一个数。批量场景下，最划算的策略不是每个数单独判断质数，而是提前把接下来要用到的所有质数信息一次性算好，后面所有判断都直接查表。这就是筛法的核心思想：空间换时间。
2.2 筛一次，查一整场
先读入所有输入，找出这组数里的最大值 maxVal。比如输入是 4、6、10、12、15、17，最大值是 17。然后只筛到 17，把 0 到 17 里哪些是质数标记出来。这一步做完，后续每个 x 判断时，判断“某个数是不是质数”就变成了 O(1) 的查表。
筛法一般用埃氏筛就行，核心思想是：从 2 开始，用每一个质数去标记它的倍数，被标记的数就是合数。剩下的没被标记的就是质数。埃氏筛的复杂度是 O(n log log n)，在 n = 10^6 时非常快，一秒钟之内能跑完。
筛法的实现里有个经典细节：外层循环 i 从 2 开始，当 isPrime[i] 为 true 时，内层循环 j 从 i × i 开始，而不是从 2 × i 开始。因为小于 i × i 的 i 的倍数，已经被比 i 更小的质因子标记过了。这个优化能把筛法常数降低不少，也符合“用质数筛倍数”的语义。
2.3 “两个素数的乘积”等价怎么用代码表达
判断 x 是不是两个质数的乘积，最直接的等价做法是：
- 枚举 x 的质因子 p，这里只需要枚举到 sqrt(x)，因为如果 x 能拆成两个质数相乘，至少有一个因子不超过 sqrt(x)。
- 枚举到一个因子 p 时，如果 p 不是质数，跳过。
- 看 x / p 这个数是不是质数，如果是，就说明 x 能拆成 p × (x/p)，两个都是质数，所以答案是 YES。
这个逻辑有一个隐藏好处：对于任意一个合数 x，你枚举到 x 的第一个因子 p 后，其实并不需要遍历完所有因子。因为如果 x 是半素数，它的质因子只有两个（可能有重复），那么第一个枚举到的质因子 p 对应的 x/p 如果是质数，就已经能给出结论了。万一 x 不是半素数，比如 x = 30 = 2 × 3 × 5，你枚举到 p = 2 时，x/p = 15 不是质数，所以不是；枚举到 p = 3 时，x/p = 10 也不是质数；枚举到 p = 5 时，x/p = 6 也不是质数。所以必须枚举到 sqrt(x)，但只要结合“找到因子就用质数表判断另一半”，每次判断都是 O(1)。
还有更巧的做法：对每个质数 p，把它的标记往后延展。比如先筛完质数，然后用两层循环枚举所有质数对 (p, q)，把 p × q 标记为“是后代”。这个做法直观，但枚举质数对的复杂度是 O(质数个数²)，在 MAX 为 10^6 时质数个数约 7.8 万，完全跑不动。所以更推荐“枚举因子 + 质数表查另一半”的方案。
3. 核心实现细节与代码落地
3.1 数据规模感知与预处理上界
开工之前先明确输入范围：MAX 到底多大？这个直接决定筛法数组开多大。
如果题目没说，最稳妥的做法是先读入所有数字，暂存到数组里，同时维护一个 maxVal。然后筛法数组 vector<bool> isPrime(maxVal + 1, true) 即可。这样可以避免写死一个大数组，也不会因为预估过小导致越界。
为什么强调先读全部再求最大值？因为如果边输入边判断，而筛法数组还没建好，就会面临一个尴尬：判断某个因子是不是质数时没有表可查。所以要么先全部读入再筛，要么干脆开一个足够大的固定数组。两种做法都可以，但先读全部再筛，理论上更节省时间，也更好把控边界。
3.2 埃氏筛的注意点
埃氏筛的标准写法：
vector<bool> buildPrimeTable(int n) { vector<bool> isPrime(n + 1, true); if (n >= 0) isPrime[0] = false; if (n >= 1) isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } return isPrime; }几个细节：
- 0 和 1 要单独置为 false。这个太容易漏了，我见过很多人筛完之后 isPrime[0] 和 isPrime[1] 还是 true，后面一出错就怀疑人生。
- i * i 有溢出风险。如果 n 接近 2×10^9，i*i 会溢出 int。稳妥点写法是用 long long 存，或者改成
i <= n / i。 - 内层循环起点是 i * i 而不是 2 * i，这是埃氏筛的经典常数优化，前面说过原因：小于 i*i 的倍数已经被更小的质因子标记过了。
如果 MAX 比较小，比如只有几百，那你随便写都行；但既然写工程代码就要有工程习惯，边界和溢出一次到位。
3.3 完整参考代码（C++）
我给出一个完整可用的版本，逻辑非常清晰：
#include <bits/stdc++.h> using namespace std; vector<bool> buildPrimeTable(int n) { vector<bool> isPrime(n + 1, true); if (n >= 0) isPrime[0] = false; if (n >= 1) isPrime[1] = false; for (int i = 2; i <= n / i; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } return isPrime; } bool isSemiprime(int x, const vector<bool>& isPrime) { if (x <= 3) return false; // 0、1、2、3 都不是 for (int p = 2; p <= x / p; p++) { if (x % p == 0) { if (isPrime[p] && isPrime[x / p]) { return true; } } } return false; } int main() { int n; cin >> n; vector<int> nums(n); int maxVal = 0; for (int i = 0; i < n; i++) { cin >> nums[i]; maxVal = max(maxVal, nums[i]); } vector<bool> isPrime = buildPrimeTable(maxVal); for (int x : nums) { cout << (isSemiprime(x, isPrime) ? "YES" : "NO") << "\n"; } return 0; }这段代码有几个地方值得说：
isSemiprime里先判x <= 3直接 false，因为 2、3 本身是质数，0、1 不用多说。但不包括 4，因为 4 = 2 × 2 是正儿八经的后代。- 循环条件是
p <= x / p，也就是p * p <= x，这样不会漏掉平方情况。 - 找到第一个因子后，并不
break，而是继续往后找。为什么？因为如果第一个因子 p 对应 x/p 不是质数，不代表后面没有别的因子组合。比如 x = 18，p = 2 时 x/p = 9 不是质数，不 break；p = 3 时 x/p = 6 也不是质数；最终输出 NO。而 x = 6，p = 2 时 x/p = 3 是质数，就输出 YES。 - 由于 x 最大不超过表的范围，
x / p也一定在表范围内，不需要额外判断越界。
这套代码对每一个 x 的循环次数不会超过 sqrt(x)，而判断因子是不是质数只是查 bool 数组，所以整体复杂度是 O(maxVal log log maxVal + m × sqrt(maxVal))，在 10^6 这个量级表现很好。
3.4 Python 版本的关键差别
如果你用 Python 写，思路一模一样，但有两个地方要注意。
第一个是筛法实现。Python 里用列表[True] * (n + 1)会比bytearray慢，也占内存。更专业的做法是用bytearray(b'\x01')：
def build_prime_table(n): is_prime = bytearray(b'\x01') * (n + 1) if n >= 0: is_prime[0] = 0 if n >= 1: is_prime[1] = 0 for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: start = i * i step = i is_prime[start:n + 1:step] = b'\x00' * (((n - start) // step) + 1) return is_prime第二步切片赋值的写法有点炫技，但确实很快。如果觉得不好读，改成常规循环也完全能用。
第二个是判断函数的写法：
def is_semiprime(x, is_prime): if x <= 3: return False p = 2 while p * p <= x: if x % p == 0 and is_prime[p] and is_prime[x // p]: return True p += 1 return FalsePython 的 while 循环比 for + break 在这个场景下更可控，而且p * p <= x也天然避免了开方精度问题。注意x // p要取整，否则浮点数拿去当 list 下标会直接报错。
4. 常见问题与排查技巧
4.1 边界值：0、1、负数、质数本身
这是新手重灾区。整理一个速查表：
| 输入 | 原因 | 结果 |
|---|---|---|
| 0 | 不是质数不是合数，无法拆成两质数乘积 | NO |
| 1 | 同上 | NO |
| 2 | 质数，只能拆成 1×2，1 不是质数 | NO |
| 3 | 质数，同理 | NO |
| 4 | 2×2，两因子都是质数 | YES |
| 6 | 2×3 | YES |
| 9 | 3×3 | YES |
| 12 | 2×6（6非质数）、3×4（4非质数） | NO |
| 25 | 5×5 | YES |
如果你发现程序把 2、3 也判成 YES，基本就是没有做“x <= 3 直接 false”这一步。如果你发现程序把 12 判成 YES，那多半是枚举因子时枚举到 1 了，因为 1 在你的表里可能不小心是 true，而 12 / 1 = 12 恰好是合数，但 12 不是质数，所以真正的错误是 1 被当成质数。
负数在绝大多数题目里不会出现，但为了健壮，可以在输入后先判断x <= 1直接 NO。
4.2 超时的元凶不是筛法，而是重复做无用功
有个非常典型的反例是：每次判断一个数时，临时调一个isPrime()函数去做试除，然后再调用buildPrimeTable()重新筛一遍。筛一遍还好，但如果把“筛表”放在循环内部，每次判断都重筛，复杂度直接爆炸。
我自己见过某开发者的代码，他写的是：
for (int i = 0; i < n; i++) { vector<bool> isPrime = buildPrimeTable(maxVal); for (...) { /* 判断 */ } }筛法放在 for 循环里，n 一多就超时。正确姿势是只筛一次，建完表后面只用不动。
另一个容易忽略的点：如果同一个数在输入里出现多次，比如题目给了 100 次 6，你的程序就要对 6 做 100 次同样的循环。这个可以用一个记忆化数组优化，把这些数算过一次之后存起来，后面直接返回结果。这个优化对于“输入里重复数字多”的数据效果明显。
4.3 常见错误速查表
整理成表格，方便你对号入座：
| 错误现象 | 大概率原因 | 修复方案 |
|---|---|---|
| 2、3 被判为 YES | 没有排除质数本身 | 在判断函数开头处理 x <= 3 |
| 12、18 被判为 YES | 把 1 当成质数，或者没有判断另一半因子是否为质数 | 检查质数表的 0、1 初始化 |
| 大范围数据超时 | 筛法在循环内重复执行 | 把筛表提升到主循环外，一次构建 |
| 数组越界 | 输入的某个数比筛表上限还大 | 先读入全部数据，取最大值作为表长 |
| 输出反了 | 逻辑写成了“找到两个因子都不是质数才 YES” | 重新对照定义，两个因子必须是质数才 YES |
| 漏掉 4、9 这种平方数 | 循环条件写成p * p < x而不是<= | 改为p * p <= x或p <= x / p |
第 4 行值得多说一句：如果某个输入 x 比 maxVal 还大，访问isPrime[x / p]时就会越界。常见原因是忘记先求 maxVal，而是拿默认值 100 去筛，结果输入里来了个 1000。这种问题编译期不报错，运行期看脸，运气好不崩，运气不好直接运行错误。所以“先读全部、再求最大值、再筛表”这条顺序非常重要。
5. 从这道题往外走：优化与变体
5.1 线性筛替代埃氏筛
埃氏筛已经很快，但它有一个小缺陷：一个合数会被它的多个质因子重复标记。比如 12 会被 2 标记一次、被 3 标记一次。线性筛（欧拉筛）可以做到每个合数只被它的最小质因子标记一次，复杂度严格 O(n)。
线性筛代码：
vector<bool> buildPrimeTableLinear(int n) { vector<bool> isPrime(n + 1, true); vector<int> primes; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; i++) { if (isPrime[i]) primes.push_back(i); for (int p : primes) { if (i * p > n) break; isPrime[i * p] = false; if (i % p == 0) break; } } return isPrime; }这个版本在 n = 10^7 以上时优势明显。但对于“质数的后代”这道题，通常 MAX 也就 10^5、10^6，埃氏筛足够用。我在面试和比赛里一般直接用埃氏筛，除非题目明确要求大范围。
5.2 大范围场景下的素数判定
如果题目把数据范围拉到 10^9 甚至 10^12，筛法就彻底吃不消了。这时有两个思路：
第一，用 Miller-Rabin 做快速素数判定。它是概率算法，但对 int64 范围内的数，取固定的几个基就能做到确定性判定。这样判断“x/p 是不是质数”时就无需筛表，麻袋里随时掏出来用。
第二，先对 x 做小因子试除，只试除到 x 的立方根附近，然后判断剩余部分是否为一个质数的平方、或者本身就是质数。这类做法的本质是：半素数的数量很少，枚举策略可以更聪明。
不过写这种代码前要先确认题目范围，不然属于过度设计。对付大多数题目，埃氏筛已经绰绰有余。
5.3 面试官爱问的变体
统计区间 [L, R] 内“质数的后代”数量。解法是筛一遍，标记所有半素数，然后做前缀和。这样单次查询 O(1)，总复杂度 O(MAX log log MAX)。
判断一个数是否能拆成两个不同质数的乘积。这时多一个条件：p != q。实现上很简单，找到组合后判断
p == q时返回 false 即可。给定 n，求第 k 个“质数的后代”。这个可以把半素数全部生成出来，排序，再二分查第 k 个。生成方式是用双指针枚举质数对 p×q，控制 p <= q 去重。
类似“三个质数乘积”的问题。判断的时候可以递归，或者先把一个因子拆出来，再判断剩余部分是否为半素数。本质是套娃，但复杂度会多一层枚举。
这些变体思路都不复杂，难的是把“筛一次、查全场”的思想迁移到位。只要理解了预处理的价值，遇到任何批量质数相关题目都能顺手解决。
6. 写在最后的一点经验
刷了这么多算法题，我对这种“包装名很怪、内核很基础”的题目特别有感情，因为它最考验一个基本能力：能不能拨开题面这层皮，看到背后其实是在考素数筛和因数拆分。
我个人的一个实际心得是，做这类题时别急着写代码，先在草稿纸上写出 0 到 30 里面所有符合条件的数：4、6、9、10、14、15、21、22、25、26。写完之后观察这些数的共同点，你自然就会发现代码里最关键的循环条件是p * p <= x而不是p <= x。这个观察能帮你避免一大半逻辑错误。
另外，筛表建完之后，建议顺手打印一下isPrime[0]、isPrime[1]看看是否符合预期。因为很多边界问题都是基础表错了，导致后续一整片结果全错。我踩过无数次这个坑，后来习惯成自然，每个筛法写完先自测这几个边界值。
最后想说的是：这类题虽然简单，但它是一个很好的“算法热身操”。它训练的是批量预处理的思维、边界条件的敏感度，以及在不超时的前提下如何把常数压到最小。把这三点练扎实了，后面遇到更复杂的数论题，你也会比别人从容得多。
