把东华OJ的题库翻到第100题名字叫“纯粹合数”第一眼看到这个题我脑子里冒出来的想法是这不就是判断合数然后筛一遍就行了等我真正把题面读清楚才发现“纯粹”两个字的含义比我想象的复杂得多——它要求一个数的每一位数字本身也必须是合数。也就是说光是判断整个数是不是合数远远不够还得管到数字的“零件”。这道题用C做下来其实是一个典型的“题目看着简单、想快速AC还得动点脑子”的题。它既考了质数判断的基本功又考了枚举策略的选择还顺便磨了一下输出格式这种容易被忽略的细节。今天就把我的完整思路、两种解法、踩过的坑一次说清楚。1. “纯粹合数”的数学定义数字级合法性才是真正的考点1.1 拆解题意从“合数”到“每一位都是合法数字”先说合数本身的定义一个大于1的自然数如果除了1和它自身之外还有其他因数就称为合数。换句话说它不是质数而且不是0和1。这个大家都熟但“纯粹合数”的条件是两层第一层整个数必须是合数。比如 46 是合数2 × 23满足第一层。第二层这个数的十进制表示中每一位数字都必须是合数。4 和 6 本身都是合数所以 46 就是一个纯粹合数。再比如 4894、8、9 三个数字全是合数489 本身等于 3 × 163也是合数所以 489 也是纯粹合数。那什么情况下会挂在第二层举个反例325。325 本身是合数5 × 65但数字里有个 33 是质数不是合数所以 325 不是纯粹合数。再比如 27 这种2 和 7 都是质数哪怕 27 是合数也完全不满足纯粹条件。到这里就能发现这道题真正需要盯住的不是“合数判断有多难”而是“哪些数字能出现在这种数的每一位上”。1.2 边界值辨析0、1、2、3、5、7为什么不能出现在纯粹合数里按数学定义0 和 1 既不是质数也不是合数所以永远不能算作“合数数字”。剩下的一位数里2、3、5、7 都是质数也进不了候选集合。所以真正能用的个位数字只有四个4、6、8、9。这个结论是整个题目的突破口。你想四位纯粹合数其实就只能由 4、6、8、9 这四个数字拼出来每一位都只能从这四个里选。这么一想枚举范围瞬间从“所有四位整数”缩小到 4 × 4 × 4 × 4 256 种排列这个数量级对计算机来说压根不算事。我第一次做这道题时就是被“纯粹”这个词绕了一下差点把 2 也算进去因为潜意识里总觉得 2 是偶数、应该算合数。但质数的定义很明确质数是大于1且只有1和自身两个正因数的自然数。2 只有 1 和 2 两个因数所以它是质数。这一点如果没搞清楚后面程序跑出来的结果肯定是错的。2. 初版暴力解法直观三层循环与复杂度分析2.1 判断一个数是否为合数的函数实现既然是算法题最稳妥的起步方式是先写一个暴力版本保证答案正确再考虑优化。暴力思路很简单从 1000 到 9999 遍历每个数先判断这个数本身是不是合数再拆出每一位判断每个数字是不是落在 {4, 6, 8, 9} 里。两个条件都满足就记录并输出。判断合数这事先判断是不是质数再取反就行。C代码可以这样写#include iostream using namespace std; bool isPrime(int x) { if (x 2) return false; // 0和1不是质数 for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; } bool isComposite(int x) { return x 2 !isPrime(x); } bool isLegalDigit(int d) { return d 4 || d 6 || d 8 || d 9; }注意i * i x这个写法它的意思是只需要检查到根号 x 即可。因为如果 x 有一个大于根号 x 的因数那必然同时存在一个小于根号 x 的因数从小的那个开始试就能试出来。用i * i x而不用i sqrt(x)是为了避免浮点运算可能带来的精度误会比如某些边界值刚好在根号附近时浮点舍入可能导致循环多跑一圈或少跑一圈。2.2 逐位拆分与数字合法性判断有了辅助函数主逻辑就清爽了int main() { bool first true; for (int n 1000; n 9999; n) { if (!isComposite(n)) continue; // 第一层整个数必须是合数 bool ok true; int t n; while (t 0) { // 第二层每一位都必须是合数数字 if (!isLegalDigit(t % 10)) { ok false; break; } t / 10; } if (ok) { if (!first) cout ; first false; cout n; } } cout endl; return 0; }这个写法里t % 10取出当前最低位判断完就t / 10把这一位丢掉循环到数字取完为止。对四位整数来说就是循环四次逻辑不需要任何额外数组。输出部分用空格分隔、末尾统一换行符合多数OJ的常规要求。2.3 暴力的代价时间复杂度与可优化点暴力版本要遍历 9000 个数每个数判断合数时要跑最多sqrt(n)次除法也就是大约 100 次。总计算量在 90 万次除法的量级这个数字对现代CPU来说微不足道东华OJ 上直接提交也能过。但如果你想追求更优雅的解法或者想把这类题目的通用思路练熟暴力版本还有两个明显的可优化点第一个点是质数判断被反复执行了 9000 次里面有大量重复计算。比如判断 1000 是合数时会试除判断 1001 是合数时又要重新从 2 开始试完全没有复用前面的结果。第二个点是遍历了 9000 个数但真正可能满足“每一位都是4、6、8、9”的数只有 256 个。也就是说绝大部分遍历工作是在浪费——那些含 0、1、2、3、5、7 的数字在第一轮就注定了不满足条件却被白白检查了个遍。所以更聪明的做法是把“生成候选数”和“判断合数”解耦。3. 欧拉筛预处理合法数字枚举把两件事彻底解耦3.1 为什么质数判断可以用“查表”替代既然我们处理的最大范围不超过四位数9999完全可以在程序一开始就用筛法把所有质数标记出来之后判断一个数是不是质数只需要查一次布尔数组时间复杂度为 O(1)。这就是典型的“空间换时间”预先把知识整理成表后面每次查询都直接翻答案。筛法里我推荐欧拉筛线性筛它的思想是保证每个合数只被它的最小质因子筛掉一次所以整体复杂度是 O(n)。相比之下埃拉托斯特尼筛法虽然代码更短但每个合数可能被多个质数重复标记虽然实际应用中差别不大但从学习角度了解欧拉筛更能加深对“唯一分解定理”的理解。欧拉筛的C实现const int MAXN 10000; bool isPrime[MAXN]; void eulerSieve(int n) { vectorint primes; for (int i 0; i n; i) isPrime[i] true; 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; // 核心保证每个合数只被最小质因子筛掉 } } }筛完之后isPrime[4999]就能直接告诉我们 4999 是不是质数不再需要任何循环除法。这个“把判断变成查表”的思路在很多数字相关的算法题里都能用到。3.2 基于4个合法数字拼接候选值然后我们改变枚举思路不再遍历 9000 个四位数而是直接用 {4, 6, 8, 9} 四个数字做四层循环拼出所有可能的四位候选值。这样做的好处是从源头就保证了每一位都合法连拆位判断都省了。int main() { eulerSieve(9999); const int digits[4] {4, 6, 8, 9}; int res[1000]; int cnt 0; // 四层循环每位只从4、6、8、9里选 for (int a 0; a 4; a) { for (int b 0; b 4; b) { for (int c 0; c 4; c) { for (int d 0; d 4; d) { int num digits[a] * 1000 digits[b] * 100 digits[c] * 10 digits[d]; // 直接查表判断是不是合数等价于 isComposite(num) if (num 2 !isPrime[num]) { res[cnt] num; } } } } } // 升序输出结果空格分隔 for (int i 0; i cnt; i) { if (i) cout ; cout res[i]; } cout endl; return 0; }由于生成时从千位到个位都是按 4、6、8、9 的顺序嵌套循环得到的候选值天然是从小到大排列不需要额外排序。这一点和暴力遍历法是一样的都是升序。3.3 两种解法的性能实测对比我在本地跑了两组数据结果如下解法候选数枚举规模质数判断方式大致时间暴力遍历逐个试除9000个四位数每个数最多约100次除法约 1-2 ms欧拉筛合法数字拼接256个四位数每次查表 O(1)0.1 ms 以下说实话对这道题的数据范围两种解法提交到OJ上都能过性能差异肉眼几乎看不出来。但第二种解法的价值在于它体现了一种更通用的思考方式——先用数学条件缩小搜索空间再引入预处理手段消除重复计算。这种思路以后遇到“满足某些数字特征”的题目时全都是同一个套路。4. 合数判断的工程细节sqrt上限、函数复用与防呆设计4.1 sqrt(9)3的边界问题用试除法判断质数时循环结束条件写成i * i x的另一个原因是避免浮点误差。拿 x 9 举例sqrt(9) 精确等于 3但如果某个实现里sqrt(9)返回 2.999999999然后循环条件写i sqrt(x)当 i 3 时循环可能直接跳出导致 9 被误判成质数。当然在实际环境中sqrt(9)返回 3.0 的概率极高但写算法一定要考虑最坏情况。用i * i x完全是整数运算不存在精度问题。这也是很多有经验的选手默认的写法。另外要注意试除法里 i 从 2 开始不考虑 1。因为1是所有数的因数用它试除没有任何区分度。4.2 把质数表当成“知识库”来用如果你用的是欧拉筛方案那isComposite这个函数其实可以写得非常朴素bool isComposite(int x) { return x 2 !isPrime[x]; }这里x 2是必须的因为筛法里isPrime[0]和isPrime[1]都被标成了 false如果直接写!isPrime[x]0 和 1 也会被误判成合数这不符合数学定义。看边界条件在任何方案里都躲不掉。这种防呆设计的价值在于它让程序对脏数据也有一定鲁棒性。比如以后你把这段逻辑抽出去做范围更大的计算传入的数是负数或者0也不会产生错误输出。写算法题不要只盯着“这次能过”把函数设计得健壮一点以后反复用的概率很高。还有一个小经验如果你把isPrime数组声明成局部变量记得初始化如果声明成全局数组C 默认会初始化为 0false但为了可读性我还是会在筛法里显式赋值。全局变量 显式初始化这是最不容易出错的组合。5. 输出格式与OJ提交的隐蔽扣分点5.1 升序输出是隐含要求这道题题面里通常不会专门强调“升序”但从结果展示的角度OJ的裁判程序一般会按照严格字符串匹配来比对输出。如果你的结果顺序和标准答案不一致哪怕数字全对也会被判 Wrong Answer。暴力法按 1000 - 9999 正序枚举天然升序拼接法因为嵌套循环的顺序是 4 - 6 - 8 - 9也天然升序。所以只要不手滑把循环顺序改了一般不会出问题。但如果你用了别的枚举方式比如把数字存进 set 后遍历或掉进容器顺序的坑那就可能输出乱序。我的习惯是无论题面是否明确要求升序都按升序输出。这不仅仅是迎合裁判也是让人类检查答案时更舒服。5.2 空格、换行、末尾多余输出的处理输出格式的细节包括三点第一数字之间用什么分隔。常见的是空格分隔也有题要求换行。如果你不确定看样例输出的最后一行有没有多余空格——样例里往往藏着答案。第二行末是否有空格。很多OJ的裁判程序会忽略行末空格和末尾换行差异但也有些严格要求逐字节一致。稳妥的做法是第一个数字前不打空格之后每个数字前打一个空格这样最后一个数字后没有多余空格。上面代码里的if (i) cout ;就是干这个的。第三禁止输出额外信息。比如“共有 87 个纯粹合数”这种提示性语句在本地调试时很有用提交前一定要注释掉或删掉否则一律判错。我自己在这里吃过亏。有一次我为了调试方便在程序里加了cout count: cnt endl;本地跑起来很爽结果提交的时候忘了删白送了一发 WA。后来我养成一个习惯调试输出全部用cerr因为cerr走的是标准错误流OJ 比对输出的时候通常只比对cout对应的标准输出流这样即使忘了删调试代码也不会影响判题结果。6. 我在刷这题时实际踩过的坑与调试过程6.1 第一次提交答案错误原因是把2当成了合数说说我第一次做这个题的真实经历。最开始我手里的候选数字集合写的是{2, 4, 6, 8, 9}我当时的想法是2 是偶数啊偶数不都是合数吗结果程序跑出来一堆奇奇怪怪的结果比如 2222 被输出了但它明明是合数同时每一位都是 2……按我的逻辑它确实算“纯粹合数”但数学定义不认这个账。后来我一查定义才反应过来质数是只有1和自身两个因数的数而 2 只有 1 和 2 两个因数所以它是质数偶数不一定是合数2 就是唯一的偶质数。这个知识点初中就学过但写代码时人的直觉经常会压过课本知识。所以这题的第一个坑恰恰是最基础的定义。做算法题时凡是涉及数学定义的判断务必以定义为准不要依赖直觉。6.2 用手算小数据集验证算法正确性为了验证程序对不对我建议先不算四位数把问题缩小到一位数和两位数手算几个结果再反推程序是否一致。比如两位数纯粹合数从 44、46、48、49、64、66、68、69、84、86、88、89、94、96、98、99 这些组合里筛选44 是合数且两位都是合数 - 符合46 是合数 - 符合48 是合数 - 符合49 7 × 7 是合数 - 符合64 是合数 - 符合66 是合数 - 符合68 是合数 - 符合69 3 × 23 是合数 - 符合84 是合数 - 符合86 是合数 - 符合88 是合数 - 符合89 是质数 - 不符合94 是合数 - 符合96 是合数 - 符合98 是合数 - 符合99 是合数 - 符合所以两位数纯粹合数一共 15 个唯一的例外是 89。这个例子可以很好地验证你的合数判断函数。我在本地测试时先只跑isComposite函数打印 2 到 100 里所有的合数跟手写的结果比对再单独跑isLegalDigit确认候选集合只有 4、6、8、9。分步验证比一次性看最终输出要容易定位问题。如果你发现两位数结果和自己手算不一致那就逐层排查别直接看四位数结果。6.3 扩展思考如果题目改成“纯粹质数”或任意位数怎么办做完这题之后可以顺手做一个小扩展如果题目改成“输出所有四位纯粹质数”你会怎么改思路其实完全一样先把候选数字集合从 {4, 6, 8, 9} 换成质数数字 {2, 3, 5, 7}再把判断条件从“是合数”改成“是质数”其余代码结构完全不用动。这就是把数字合法性和整个数的属性解耦带来的好处两套逻辑互不干扰。如果题目改成“输出1000以内所有纯粹合数”那就把枚举范围的边界改一下循环层数从四层改成三层或者直接用一位数/两位数/三位数分别拼接。这类变体在OJ里经常出现掌握“构造合法候选 查表判断属性”的组合拳几乎所有这类题都能轻松应对。回头再看这道“纯粹合数”它真正的难点从来不是“判断合数”这个动作而是你能不能把“位数字合法性”和“整个数属性”当成两个独立维度来处理。想通了这一点代码量反而比暴力版本更少思路也更清晰。如果你正在刷东华OJ的基础题遇到类似这种“XX数”的题目我建议你统一走这个流程先把数学定义严格划清边界再决定是遍历还是构造候选数最后用筛法或查表优化重复计算。这套流程下来不只是这一道题后面很多数论题都能少走弯路。