第一次在训练题单里看到质数的后代这个标题时我的第一反应是这不就是对每个数做一次质因数分解吗后来仔细读了括号里的补充——合数为两个素数的乘积——才发现题目真正想考的并不是你背熟了埃氏筛而是你能不能把一个生活化的概念翻译成可判定的数学条件。所谓质数的后代就是半素数semiprime一个合数恰好能写成两个素数的乘积这两个素数可以相同比如42×2、62×3、153×5。换句话说它的质因数分解中带重数统计的质因子个数恰好为2。这篇文章会从题目语义拆起逐步给出暴力写法、筛表写法、线性筛细节、边界条件最后放一份可直接提交的模板和本地对拍方法。适合正在刷算法提高题、准备机试或者想彻底搞明白素数与合数关系的读者。1. 先看清题目合数拆成两个素数本质是半素数判定1.1 从质数的后代这个说法说起质数的后代是一个容易被名字带偏的题。很多人一看到质数两个字就下意识去写素数判定模板然后对输入n直接判断它是不是质数。这完全跑偏了。题目要判断的是给定一个合数n它能不能由两个素数相乘得到。比如213×7那21就是质数的后代182×3×3它需要三个素数相乘所以不是。这个定义和n本身是不是质数没有直接关系甚至可以说n本身是质数时反而一定不是后代因为质数不能被拆成两个大于1的整数相乘。为了降低理解成本可以看一下前半段例子n分解是否为质数的后代42×2是62×3是93×3是102×5是122×2×3否153×5是213×7是302×3×5否从表格能清楚看到关键不是能不能被某个质数整除而是分解到底要消耗几个质数因子。两个质数刚刚好多于两个就出局。这个概念在数论里有个现成名字叫半素数很多数学资料里也叫双素数或二质数乘积。竞赛题不会直接用这个名词而是包装成质数的后代本质上就是让你做半素数判断。1.2 把自然语言翻译成可判定条件做算法题的第一步永远是翻译条件。题目的表述是一个合数可以写成两个素数的乘积。翻译成数学语言就是存在素数p和q使得np×q并且n是合数。因为乘法交换律p、q顺序无所谓所以可以规定p≤q枚举时只需要考虑一半的情况。这里有一个特别重要的简化如果n是合数那么它一定有最小质因子p。令qn/p那么n是否等于某两个素数乘积可以直接等价于q是否为素数。为什么能这么简化因为p是n的最小质因子p自己一定是素数。一个合数因子不可能是n的最小因子假设d是n的合数因子那么d一定有一个比d更小的真因子d0而d0也能整除n所以从小到大扫描时先遇到的肯定是d0而不是d。既然第一次遇到的因子就是最小质因子剩下的工作就只有一件事——检查另一个因子q是不是素数。反过来如果q是素数那么np×q已经满足定义直接判true。如果q不是素数说明n至少拥有三个带重数的质因子也不需要再找其他分解了。这个简化是整道题的核心。很多人把这道题写复杂是因为一上来就想做完整质因数分解统计质因子个数再判断是否等于2。完整质因数分解当然也能做但它需要枚举每一个因子并维护幂次代码量明显更大。而利用最小质因子天然是素数这个性质只需要一次整除判断加一次素数判断。2. 从双重枚举到查表三种实现思路的复杂度递进2.1 最直观的双重枚举先保证写对如果只追求正确性第一版可以写得很朴素从小到大找能整除n的数p找到后判断qn/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)。这是最容易被忽略的优化写对之后能省掉一半的时间复杂度。为什么n4可以直接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; vectorint 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的素数对把乘积位置标成truebool 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变大乘积只会更大没有必要继续。这个方案的预先生成时间看起来吓人实际很轻。以MAXN10^6为例外层p只需要枚举到1000因为p×p≤10^6内层q的个数则随着p变大逐渐减少总循环量大约在几十万量级和筛法本身差不多。预处理完成之后每个查询只需要返回isDesc[n]复杂度O(1)。三种思路的比较如下方案单次查询时间预处理适合场景直接试除法O(sqrt(n))无单次或极少量查询素数表 试除O(π(sqrt(n)))筛MAXN多组查询范围较大预生成后代表O(1)筛枚举素数对查询极多上限固定实际比赛中我习惯先用直接试除法做对拍基准再根据数据范围决定要不要预处理。如果题目没给具体范围稳妥做法是第2.2节的素数表方案。3. 线性筛的两个关键点为什么不会重复标记、如何减少试除3.1 欧拉筛为什么不会重复标记埃氏筛写起来最简单但有个小毛病同一个合数会被不同的质因子重复标记。比如12i2时标记12i3时又标记12。当MAXN到10^7甚至更大时重复标记带来的额外循环会让常数变大。线性筛也叫欧拉筛可以保证每个合数只被它的最小质因子筛掉一次。核心代码如下vectorint 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就停下来把标记权留给更小的质因子。举一个具体例子。i6时primes表里的p先等于2标记12然后发现6%20break不再用p3去标记18。18应该由i9和p2来标记。这样每个合数都只被标记一次总复杂度从O(NloglogN)降到严格的O(N)。N不太大的时候两者差异不大但线性筛的逻辑更干净也更容易推导出最小质因子相关的信息。3.2 筛出素数表后枚举量少了一个数量级筛法的作用不只是生成一张谁是素数的表它同时生成了从小到大排列的素数列表。这个列表正好是试除法的候选集合。想象一下如果不用素数表从2到sqrt(n)之间可能有大量的偶数、9的倍数、15的倍数等等。这些合数永远不可能成为n的最小质因子但你依然要对它们做一次取模运算。使用素数表之后这些无效尝试全部被跳过。这里还有一处可以进一步剪枝找到第一个能整除n的素数p后直接判断qn/p是否为素数并返回结果不需要继续枚举后面的素数。原因在前面已经讲过第一个整除n的p就是最小质因子q一旦不是素数n的带重数质因子个数已经超过2后面不会再出现另一种分解让它变成半素数。很多人在这一步会犹豫觉得应该把n完全分解完再看。实际上完全分解是多余的还会引入不必要的状态记录。如果n本身是素数整个循环会一直跑到p*p n都没有找到因子最后返回false。这个返回结果是正确的因为素数当然不是两个素数的乘积。4. 边界条件与常见翻车现场0、1、素数本身、平方数怎么办4.1 合数定义带来的第一道坎题目说的是合数为两个素数的乘积所以判断之前先要理解合数的范围。合数指大于1且不是质数的自然数。按这个定义0不是自然数的情形就不讨论1既不是素数也不是合数2和3是素数也不是合数。把这些数全部判为false似乎很自然但写代码时如果不加n4的判断很容易在某些实现里出问题。例如有人在check函数里这样写从p2开始试除如果整除就判断q如果一直到sqrt(n)都没整除就返回true理由是没有因子说明是素数。这种逻辑在n2、3、5时会错误返回true。所以要么在开头用if (n 4) return false;拦住所有小于4的输入要么在循环结束后明确写到这里说明n是素数返回false。推荐把n 4放到第一行。它不仅是边界保护也是语义表达最小能被两个素数相乘得到的合数是4。4.2 相同素数相乘的平方情况要不要算这是这种题目最容易产生歧义的地方。题目说两个素数的乘积很多人在数学直觉上倾向于认为两个素数应该不同于是42×2、93×3、255×5会被排除。但从题目标题写法看合数为两个素数的乘积并没有写两个不同的素数按数学惯例两个素数相同也算两个素数相乘所以4、9、25通常要判true。遇到不确定的题目最稳妥的办法是看样例。如果样例里出现了4却期望输出false那说明题目要求p≠q如果4期望输出true那就是允许相同。我在代码注释里一定会写清楚自己的假设比如// 按题意“两个素数”允许相等42*2 判 Yes如果题目要求互不相同改动也很小。在找到因子后if (p q) return false;一个真实的坑是有人以为平方数都算后代于是看到164×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^12MAXN取10^6#include bits/stdc.h using namespace std; const int MAXN 1000000; vectorint 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 * pcheck内1LL * p * p这两处如果不转long longMAXN10^6时还不至于溢出但一旦MAXN调到10^7甚至10^8int相乘会直接出错。这是经典的低级错误宁可每次都写也不要赌数据范围。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更划算。所谓最优解法永远是结合数据范围后选择的最合适解法。最后说一个我自己的习惯凡是和素数相关的题我都会在本地留一份线性筛模板和一份试除模板。拿到题先看数据范围如果只有一次询问直接用试除甚至不筛表如果多组询问就把筛子先拉了再查。质数的后代这道题本身不算难但它把质因数分解、素数判定、数论筛法三个知识点串在一起非常适合当作从会用模板到会挑模板的练手题。把文章里这几版代码都跑一遍、对拍一遍你对半素数这类概念的理解会比背十道模板题扎实得多。
