第一次在题库里刷到“质数的后代”这个题名时我愣了几秒质数怎么还有后代点开题面才反应过来它说的是形如 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 11 不是质数所以输出 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。然后筛法数组 vectorbool isPrime(maxVal 1, true) 即可。这样可以避免写死一个大数组也不会因为预估过小导致越界。为什么强调先读全部再求最大值因为如果边输入边判断而筛法数组还没建好就会面临一个尴尬判断某个因子是不是质数时没有表可查。所以要么先全部读入再筛要么干脆开一个足够大的固定数组。两种做法都可以但先读全部再筛理论上更节省时间也更好把控边界。3.2 埃氏筛的注意点埃氏筛的标准写法vectorbool buildPrimeTable(int n) { vectorbool 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^9i*i 会溢出 int。稳妥点写法是用 long long 存或者改成i n / i。内层循环起点是 i * i 而不是 2 * i这是埃氏筛的经典常数优化前面说过原因小于 i*i 的倍数已经被更小的质因子标记过了。如果 MAX 比较小比如只有几百那你随便写都行但既然写工程代码就要有工程习惯边界和溢出一次到位。3.3 完整参考代码C我给出一个完整可用的版本逻辑非常清晰#include bits/stdc.h using namespace std; vectorbool buildPrimeTable(int n) { vectorbool 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 vectorbool 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; vectorint nums(n); int maxVal 0; for (int i 0; i n; i) { cin nums[i]; maxVal max(maxVal, nums[i]); } vectorbool 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 18p 2 时 x/p 9 不是质数不 breakp 3 时 x/p 6 也不是质数最终输出 NO。而 x 6p 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不是质数不是合数无法拆成两质数乘积NO1同上NO2质数只能拆成 1×21 不是质数NO3质数同理NO42×2两因子都是质数YES62×3YES93×3YES122×66非质数、3×44非质数NO255×5YES如果你发现程序把 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) { vectorbool isPrime buildPrimeTable(maxVal); for (...) { /* 判断 */ } }筛法放在 for 循环里n 一多就超时。正确姿势是只筛一次建完表后面只用不动。另一个容易忽略的点如果同一个数在输入里出现多次比如题目给了 100 次 6你的程序就要对 6 做 100 次同样的循环。这个可以用一个记忆化数组优化把这些数算过一次之后存起来后面直接返回结果。这个优化对于“输入里重复数字多”的数据效果明显。4.3 常见错误速查表整理成表格方便你对号入座错误现象大概率原因修复方案2、3 被判为 YES没有排除质数本身在判断函数开头处理 x 312、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)。线性筛代码vectorbool buildPrimeTableLinear(int n) { vectorbool isPrime(n 1, true); vectorint 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]看看是否符合预期。因为很多边界问题都是基础表错了导致后续一整片结果全错。我踩过无数次这个坑后来习惯成自然每个筛法写完先自测这几个边界值。最后想说的是这类题虽然简单但它是一个很好的“算法热身操”。它训练的是批量预处理的思维、边界条件的敏感度以及在不超时的前提下如何把常数压到最小。把这三点练扎实了后面遇到更复杂的数论题你也会比别人从容得多。 
长河君 · 2026/10/15 18:08:32 · 阅读 1.2k 质数的后代：半素数判定与素数筛实现
第一次在题库里刷到“质数的后代”这个题名时我愣了几秒质数怎么还有后代点开题面才反应过来它说的是形如 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 11 不是质数所以输出 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。然后筛法数组 vectorbool isPrime(maxVal 1, true) 即可。这样可以避免写死一个大数组也不会因为预估过小导致越界。为什么强调先读全部再求最大值因为如果边输入边判断而筛法数组还没建好就会面临一个尴尬判断某个因子是不是质数时没有表可查。所以要么先全部读入再筛要么干脆开一个足够大的固定数组。两种做法都可以但先读全部再筛理论上更节省时间也更好把控边界。3.2 埃氏筛的注意点埃氏筛的标准写法vectorbool buildPrimeTable(int n) { vectorbool 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^9i*i 会溢出 int。稳妥点写法是用 long long 存或者改成i n / i。内层循环起点是 i * i 而不是 2 * i这是埃氏筛的经典常数优化前面说过原因小于 i*i 的倍数已经被更小的质因子标记过了。如果 MAX 比较小比如只有几百那你随便写都行但既然写工程代码就要有工程习惯边界和溢出一次到位。3.3 完整参考代码C我给出一个完整可用的版本逻辑非常清晰#include bits/stdc.h using namespace std; vectorbool buildPrimeTable(int n) { vectorbool 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 vectorbool 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; vectorint nums(n); int maxVal 0; for (int i 0; i n; i) { cin nums[i]; maxVal max(maxVal, nums[i]); } vectorbool 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 18p 2 时 x/p 9 不是质数不 breakp 3 时 x/p 6 也不是质数最终输出 NO。而 x 6p 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不是质数不是合数无法拆成两质数乘积NO1同上NO2质数只能拆成 1×21 不是质数NO3质数同理NO42×2两因子都是质数YES62×3YES93×3YES122×66非质数、3×44非质数NO255×5YES如果你发现程序把 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) { vectorbool isPrime buildPrimeTable(maxVal); for (...) { /* 判断 */ } }筛法放在 for 循环里n 一多就超时。正确姿势是只筛一次建完表后面只用不动。另一个容易忽略的点如果同一个数在输入里出现多次比如题目给了 100 次 6你的程序就要对 6 做 100 次同样的循环。这个可以用一个记忆化数组优化把这些数算过一次之后存起来后面直接返回结果。这个优化对于“输入里重复数字多”的数据效果明显。4.3 常见错误速查表整理成表格方便你对号入座错误现象大概率原因修复方案2、3 被判为 YES没有排除质数本身在判断函数开头处理 x 312、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)。线性筛代码vectorbool buildPrimeTableLinear(int n) { vectorbool isPrime(n 1, true); vectorint 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]看看是否符合预期。因为很多边界问题都是基础表错了导致后续一整片结果全错。我踩过无数次这个坑后来习惯成自然每个筛法写完先自测这几个边界值。最后想说的是这类题虽然简单但它是一个很好的“算法热身操”。它训练的是批量预处理的思维、边界条件的敏感度以及在不超时的前提下如何把常数压到最小。把这三点练扎实了后面遇到更复杂的数论题你也会比别人从容得多。