第一次在训练题单里看到"质数的后代"这个标题时，我的第一反应是：这不就是对每个数做一次质因数分解吗？后来仔细读了括号里的补充——合数为两个素数的乘积——才发现题目真正想考的，并不是你背熟了埃氏筛，而是你能不能把一个生活化的概念翻译成可判定的数学条件。所谓质数的后代，就是半素数（semiprime）：一个合数恰好能写成两个素数的乘积，这两个素数可以相同，比如4=2×2、6=2×3、15=3×5。换句话说，它的质因数分解中，带重数统计的质因子个数恰好为2。这篇文章会从题目语义拆起，逐步给出暴力写法、筛表写法、线性筛细节、边界条件，最后放一份可直接提交的模板和本地对拍方法。适合正在刷算法提高题、准备机试，或者想彻底搞明白"素数与合数关系"的读者。

1. 先看清题目：合数拆成两个素数，本质是半素数判定

1.1 从"质数的后代"这个说法说起

"质数的后代"是一个容易被名字带偏的题。很多人一看到"质数"两个字，就下意识去写素数判定模板，然后对输入n直接判断它是不是质数。这完全跑偏了。题目要判断的是：给定一个合数n，它能不能由两个素数相乘得到。比如21=3×7，那21就是质数的后代；18=2×3×3，它需要三个素数相乘，所以不是。这个定义和"n本身是不是质数"没有直接关系，甚至可以说，n本身是质数时反而一定不是后代，因为质数不能被拆成两个大于1的整数相乘。

为了降低理解成本，可以看一下前半段例子：

从表格能清楚看到，关键不是"能不能被某个质数整除"，而是"分解到底要消耗几个质数因子"。两个质数刚刚好，多于两个就出局。这个概念在数论里有个现成名字叫半素数，很多数学资料里也叫双素数或二质数乘积。竞赛题不会直接用这个名词，而是包装成"质数的后代"，本质上就是让你做半素数判断。

1.2 把自然语言翻译成可判定条件

做算法题的第一步永远是翻译条件。题目的表述是：一个合数可以写成两个素数的乘积。翻译成数学语言就是：存在素数p和q，使得n=p×q，并且n是合数。因为乘法交换律，p、q顺序无所谓，所以可以规定p≤q，枚举时只需要考虑一半的情况。

这里有一个特别重要的简化：如果n是合数，那么它一定有最小质因子p。令q=n/p，那么"n是否等于某两个素数乘积"可以直接等价于"q是否为素数"。

为什么能这么简化？因为p是n的最小质因子，p自己一定是素数。一个合数因子不可能是n的最小因子：假设d是n的合数因子，那么d一定有一个比d更小的真因子d0，而d0也能整除n，所以从小到大扫描时，先遇到的肯定是d0而不是d。既然第一次遇到的因子就是最小质因子，剩下的工作就只有一件事——检查另一个因子q是不是素数。反过来，如果q是素数，那么n=p×q已经满足定义，直接判true。如果q不是素数，说明n至少拥有三个带重数的质因子，也不需要再找其他分解了。

这个简化是整道题的核心。很多人把这道题写复杂，是因为一上来就想做"完整质因数分解"，统计质因子个数再判断是否等于2。完整质因数分解当然也能做，但它需要枚举每一个因子并维护幂次，代码量明显更大。而利用"最小质因子天然是素数"这个性质，只需要一次整除判断加一次素数判断。

2. 从双重枚举到查表：三种实现思路的复杂度递进

2.1 最直观的双重枚举：先保证写对

如果只追求正确性，第一版可以写得很朴素：从小到大找能整除n的数p，找到后判断q=n/p是不是素数。这里的p不需要预先筛出来，直接从2开始试除即可。

先写一个基础版本：

bool isPrime(long long x) { if (x < 2) return false; for (long long d = 2; d * d <= x; ++d) if (x % d == 0) return false; return true; } bool check(long long n) { if (n < 4) return false; for (long long p = 2; p * p <= n; ++p) { if (n % p == 0) { long long q = n / p; return isPrime(q); } } return false; }

这里有一个看似不起眼但很关键的点：p的值不保证是素数，但第一个能被n整除的p一定是最小质因子，所以p必然是素数。于是代码里不需要再调用isPrime(p)。这是最容易被忽略的优化，写对之后能省掉一半的时间复杂度。

为什么n<4可以直接return false？因为4是最小的合数，也是最小的"两个素数乘积"。0、1、2、3都不可能满足要求。这个提前返回还能顺带挡住所有输入小于4的情况，省去后面的边界判断。

这段代码的复杂度大约是O(sqrt(n))：最坏情况下要从2试除到sqrt(n)。单次查询很轻，但如果题目给了一万次查询，每次都重新试除，就会开始吃力。它适合作为第一版，用来验证思路，不适合直接拿去交大数据题。

2.2 借助素数表缩小试除范围

第二步改进是预处理一张素数表。把2到MAXN范围内的所有素数先筛出来，试除时只枚举素数。同样是在找最小质因子，但候选数从"所有整数"缩减为"所有素数"。

素数表一出来，两个操作都会被加速：第一，试除p时不用再检查那些偶数、3的倍数等合数；第二，当q不超过MAXN时，可以用查表的方式在O(1)时间内判断q是否为素数，而不是重新做试除。

埃氏筛可以这样写：

const int MAXN = 1000000; vector<int> primes; bool isComp[MAXN + 1]; void sieve() { fill(isComp, isComp + MAXN + 1, false); for (int i = 2; i <= MAXN; ++i) { if (!isComp[i]) { primes.push_back(i); if (1LL * i * i <= MAXN) for (long long j = 1LL * i * i; j <= MAXN; j += i) isComp[j] = true; } } }

注意这里用isComp表示"合数"，初始全false，筛出来的合数标记为true。判断q是否为素数时，只要看!isComp[q]，前提是q不超过MAXN。

判断函数变成：

bool check(long long n) { if (n < 4) return false; for (int p : primes) { if (1LL * p * p > n) break; if (n % p == 0) { long long q = n / p; if (q <= MAXN) return !isComp[q]; return isPrime(q); } } return false; }

枚举素数而不是整数，单次查询的最坏复杂度从O(sqrt(n))降到O(π(sqrt(n)))。当sqrt(n)等于10^6时，整数要试100万个位置，素数表只需要试约7.8万个位置，差了十几倍。这个差距在多组查询下会被放大得非常明显。

2.3 预生成"后代"集合：查询O(1)的查表法

如果题目明确说所有输入都不超过某个上限N，那还有一条更"暴力"但更快的路：直接把所有N以内的半素数预先标记出来，后续每个查询直接读标记数组。

做法是利用已经筛好的素数表，枚举所有满足p≤q且p×q≤N的素数对，把乘积位置标成true：

bool isDesc[MAXN + 1]; void buildDesc() { for (int i = 0; i < (int)primes.size(); ++i) { for (int j = i; j < (int)primes.size(); ++j) { long long v = 1LL * primes[i] * primes[j]; if (v > MAXN) break; isDesc[v] = true; } } }

这里的j从i开始，保证p≤q，同时也自然地包含平方数，例如2×2、3×3都会被标记。内层循环一旦乘积超过MAXN立刻break，因为随着j变大，乘积只会更大，没有必要继续。

这个方案的预先生成时间看起来吓人，实际很轻。以MAXN=10^6为例，外层p只需要枚举到1000，因为p×p≤10^6；内层q的个数则随着p变大逐渐减少，总循环量大约在几十万量级，和筛法本身差不多。预处理完成之后，每个查询只需要返回isDesc[n]，复杂度O(1)。

三种思路的比较如下：

实际比赛中，我习惯先用直接试除法做对拍基准，再根据数据范围决定要不要预处理。如果题目没给具体范围，稳妥做法是第2.2节的素数表方案。

3. 线性筛的两个关键点：为什么不会重复标记、如何减少试除

3.1 欧拉筛为什么不会重复标记

埃氏筛写起来最简单，但有个小毛病：同一个合数会被不同的质因子重复标记。比如12，i=2时标记12，i=3时又标记12。当MAXN到10^7甚至更大时，重复标记带来的额外循环会让常数变大。

线性筛，也叫欧拉筛，可以保证每个合数只被它的最小质因子筛掉一次。核心代码如下：

vector<int> primes; bool isComp[MAXN + 1]; void linearSieve() { for (int i = 2; i <= MAXN; ++i) { if (!isComp[i]) primes.push_back(i); for (int p : primes) { long long v = 1LL * i * p; if (v > MAXN) break; isComp[v] = true; if (i % p == 0) break; } } }

关键在于最后一行if (i % p == 0) break;。当i能被p整除时，继续用更大的素数去标记i×p，会让i×p被一个不是它最小质因子的数筛掉，将来还会被重复筛一次。所以一旦遇到能整除i的p，就停下来，把标记权留给更小的质因子。

举一个具体例子。i=6时，primes表里的p先等于2，标记12，然后发现6%2==0，break，不再用p=3去标记18。18应该由i=9和p=2来标记。这样每个合数都只被标记一次，总复杂度从O(NloglogN)降到严格的O(N)。N不太大的时候两者差异不大，但线性筛的逻辑更干净，也更容易推导出最小质因子相关的信息。

3.2 筛出素数表后，枚举量少了一个数量级

筛法的作用不只是生成一张"谁是素数"的表，它同时生成了"从小到大排列的素数列表"。这个列表正好是试除法的候选集合。

想象一下如果不用素数表，从2到sqrt(n)之间可能有大量的偶数、9的倍数、15的倍数等等。这些合数永远不可能成为n的最小质因子，但你依然要对它们做一次取模运算。使用素数表之后，这些无效尝试全部被跳过。

这里还有一处可以进一步剪枝：找到第一个能整除n的素数p后，直接判断q=n/p是否为素数并返回结果，不需要继续枚举后面的素数。原因在前面已经讲过：第一个整除n的p就是最小质因子，q一旦不是素数，n的带重数质因子个数已经超过2，后面不会再出现"另一种分解"让它变成半素数。很多人在这一步会犹豫，觉得应该把n完全分解完再看。实际上完全分解是多余的，还会引入不必要的状态记录。

如果n本身是素数，整个循环会一直跑到p*p > n都没有找到因子，最后返回false。这个返回结果是正确的，因为素数当然不是"两个素数的乘积"。

4. 边界条件与常见翻车现场：0、1、素数本身、平方数怎么办

4.1 合数定义带来的第一道坎

题目说的是"合数为两个素数的乘积"，所以判断之前先要理解合数的范围。合数指大于1且不是质数的自然数。按这个定义，0不是自然数的情形就不讨论，1既不是素数也不是合数，2和3是素数也不是合数。

把这些数全部判为false，似乎很自然，但写代码时如果不加n<4的判断，很容易在某些实现里出问题。例如有人在check函数里这样写：从p=2开始试除，如果整除就判断q；如果一直到sqrt(n)都没整除就返回true，理由是"没有因子说明是素数"。这种逻辑在n=2、3、5时会错误返回true。所以要么在开头用if (n < 4) return false;拦住所有小于4的输入，要么在循环结束后明确写"到这里说明n是素数，返回false"。

推荐把n < 4放到第一行。它不仅是边界保护，也是语义表达：最小能被两个素数相乘得到的合数是4。

4.2 相同素数相乘的"平方情况"要不要算

这是这种题目最容易产生歧义的地方。题目说"两个素数的乘积"，很多人在数学直觉上倾向于认为两个素数应该不同，于是4=2×2、9=3×3、25=5×5会被排除。但从题目标题写法看，"合数为两个素数的乘积"并没有写"两个不同的素数"，按数学惯例，两个素数相同也算两个素数相乘，所以4、9、25通常要判true。

遇到不确定的题目，最稳妥的办法是看样例。如果样例里出现了4却期望输出false，那说明题目要求p≠q；如果4期望输出true，那就是允许相同。我在代码注释里一定会写清楚自己的假设，比如：

// 按题意“两个素数”允许相等，4=2*2 判 Yes

如果题目要求互不相同，改动也很小。在找到因子后：

if (p == q) return false;

一个真实的坑是：有人以为平方数都算后代，于是看到16=4×4也判true。但16的分解是2×2×2×2，四个质因子，不是两个素数。判断时必须回到质因子层面，不能只看形式上的"两个数相乘"。

4.3 数据范围没给全时的应对策略

很多练习平台不会直接把数据范围写在标题里，只会在题目页面里给。这时最忌讳的是硬编码一个MAXN然后自信地提交。正确做法是：如果允许，先读入所有测试数据，找到最大数值，再把筛表上限设为这个最大值，或者设为sqrt(最大值)。

当输入n可能达到10^12时，筛到10^6就足够。原因很简单：如果n是两个素数的乘积，且两个因子都大于10^6，那么乘积会超过10^12。所以至少有一个因子不超过10^6，枚举最小质因子时一定会遇到它。

如果n大到10^18级别，筛1e9显然不现实，这时需要Miller-Rabin这类大数素性测试方法。但在算法提高这个级别的题里通常碰不到，知道有这条路即可。真正要做的是先看数据范围，再决定筛多深、用哪种判断，而不是拿到题就套模板。

5. 完整模板与本地对拍：竞赛代码、Python版本、验证方法

5.1 C++ 实现：直接可贴的模板

把前面所有内容整合成一份完整C++代码，假设n不超过10^12，MAXN取10^6：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000000; vector<int> primes; bool isComp[MAXN + 1]; void linearSieve() { for (int i = 2; i <= MAXN; ++i) { if (!isComp[i]) primes.push_back(i); for (int p : primes) { long long v = 1LL * i * p; if (v > MAXN) break; isComp[v] = true; if (i % p == 0) break; } } } bool bigPrime(long long x) { if (x < 2) return false; for (long long d = 2; d * d <= x; ++d) if (x % d == 0) return false; return true; } bool check(long long n) { if (n < 4) return false; for (int p : primes) { if (1LL * p * p > n) break; if (n % p == 0) { long long q = n / p; if (q <= MAXN) return !isComp[q]; return bigPrime(q); } } return false; } int main() { linearSieve(); long long n; while (cin >> n) { cout << (check(n) ? "Yes" : "No") << '\n'; } return 0; }

这段代码的读取方式是直到输入流结束。如果题目给的是多组输入格式，可以直接用。如果题目先给一个T表示询问次数，就把while(cin >> n)改成先读T再循环。无论哪种，check函数都不用变。

需要注意的细节全部藏在乘法溢出里。筛法内1LL * i * p，check内1LL * p * p，这两处如果不转long long，MAXN=10^6时还不至于溢出，但一旦MAXN调到10^7甚至10^8，int相乘会直接出错。这是经典的低级错误，宁可每次都写，也不要赌数据范围。

5.2 Python 实现：改循环前先想清楚

Python写这个题也能过，关键是别用一堆重量级封装。下面这个版本用bytearray做合数标记，内存更小：

MAXN = 10**6 is_comp = bytearray(MAXN + 1) primes = [] for i in range(2, MAXN + 1): if not is_comp[i]: primes.append(i) for p in primes: v = i * p if v > MAXN: break is_comp[v] = 1 if i % p == 0: break def big_prime(x): if x < 2: return False for p in primes: if p * p > x: break if x % p == 0: return False return True def check(n): if n < 4: return False for p in primes: if p * p > n: break if n % p == 0: q = n // p if q <= MAXN: return not is_comp[q] return big_prime(q) return False while True: try: n = int(input()) except EOFError: break print("Yes" if check(n) else "No")

这里big_prime复用素数表，只用素数去试除大数，比从2开始逐个数试快很多。前提是x不超过MAXN^2，因为平方根不会超过MAXN。如果输入范围达到10^12，这个前提依然成立。

Python版在实际提交时，预处理1e6的筛表大概是零点几秒，属于安全范围。如果MAXN到1e7，线性筛Python会比较吃力，可以考虑用埃氏筛配合bytearray的切片操作，例如用is_comp[i*i::i] = b'\x01' * ((MAXN - i*i)//i + 1)整体赋值，速度反而更好。不过算法提高题很少会逼你优化到这个程度。

5.3 本地验证：朴素对拍与性能量级

写算法题，最怕代码跑出来和预期一致其实是"都错了，错得一致"。所以本地一定要做对拍。用朴素的完全分解作为基准，和优化版check对比：

from math import isqrt def is_prime(x): if x < 2: return False for d in range(2, isqrt(x) + 1): if x % d == 0: return False return True def naive(n): for p in range(2, isqrt(n) + 1): if n % p == 0: q = n // p return is_prime(p) and is_prime(q) return False for n in range(1, 3000): if check(n) != naive(n): print("mismatch", n, check(n), naive(n)) break else: print("all ok")

naive版本里无论p是不是素数都调用is_prime去确认，这样虽然慢，但足够独立，不容易和check犯同一个错误。跑完1到3000，如果全部一致，再挑几组大数测边界，比如两个大素数乘积、大素数本身、完全平方数。这类数据往往是只测小范围时发现不了问题的。

性能上可以在本地简单计时。以我自己的机器为参考，筛1e6大约0.05秒，筛1e7大约0.5秒；用素数表做单次大数查询基本可以忽略。如果题目查询次数少，预处理时间反而可能超过直接试除的时间，这时选2.1或2.2更划算。所谓"最优解法"，永远是结合数据范围后选择的最合适解法。

最后说一个我自己的习惯：凡是和素数相关的题，我都会在本地留一份线性筛模板和一份试除模板。拿到题先看数据范围，如果只有一次询问，直接用试除，甚至不筛表；如果多组询问，就把筛子先拉了再查。质数的后代这道题本身不算难，但它把质因数分解、素数判定、数论筛法三个知识点串在一起，非常适合当作从"会用模板"到"会挑模板"的练手题。把文章里这几版代码都跑一遍、对拍一遍，你对半素数这类概念的理解会比背十道模板题扎实得多。