蓝桥杯真题解析：纯质数与完全日期的算法实现与优化

1. 从“纯质数”到“完全日期”一次蓝桥杯国赛真题的深度拆解最近在复盘蓝桥杯历届国赛真题时我重新审视了2021年那场国赛的几道题目其中“纯质数”和“完全日期”这两道题给我留下了很深的印象。它们不像某些偏门算法题那样刁钻而是非常典型地考察了选手对基础数论、日期处理以及编程基本功的综合运用能力。很多朋友在初次接触时可能会觉得“纯质数”不就是判断质数吗“完全日期”不就是算平方和吗但真正上手去写才会发现里面藏着不少细节和优化点稍不注意就会掉进坑里或者写出效率低下的代码在竞赛的时限压力下功亏一篑。今天我就结合自己的解题和教学经验把这两道题从题意理解、核心算法、代码实现到优化技巧掰开揉碎了讲清楚。无论你是正在备赛的蓝桥杯选手还是想巩固C算法基础的学习者相信这篇超过五千字的实战解析都能让你有所收获。2. “纯质数”的题意剖析与暴力解法陷阱我们先来看“纯质数”这道题。题目通常的定义是如果一个质数素数的每一位数字也都是质数即每一位只能是2, 3, 5, 7这四个数字之一那么这个数就被称为“纯质数”。题目一般会给定一个范围要求统计或找出该范围内的所有纯质数。2.1 理解“纯质数”的双重约束这道题的核心约束有两个而且是“与”的关系必须同时满足该数本身是质数这是数论的基本定义即一个大于1的自然数除了1和它自身外不能被其他自然数整除。该数的每一位数字都是质数在十进制表示下每一位上的数字必须是质数。注意这里“数字是质数”指的是数字本身的值是质数。在0-9这十个数字中只有2, 3, 5, 7是质数。因此一个纯质数的每一位只能是2、3、5、7中的一个。这里有一个非常关键的边界条件数字1不是质数数字0也不是质数因此任何包含0或1的数直接就不满足条件2无需再进行耗时的质数判断。这是一个重要的优化剪枝点。2.2 最直接的暴力解法及其效率问题最直观的思路是遍历题目给定的范围例如1到20210605对每一个数先判断其每一位是否由2,3,5,7组成如果是再判断这个数本身是不是质数。bool isPrime(int n) { if (n 1) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; } bool isPurePrime(int n) { int temp n; while (temp 0) { int digit temp % 10; if (digit ! 2 digit ! 3 digit ! 5 digit ! 7) { return false; // 有一位不是质数数字直接返回 } temp / 10; } // 所有位都是质数数字再判断n本身是不是质数 return isPrime(n); }然后主函数里循环调用isPurePrime。这个方法逻辑完全正确但对于大数据范围比如上千万其效率是灾难性的。原因在于无效的质数判断太多一个包含0,1,4,6,8,9这些非质数数字的数我们很快就能在isPurePrime函数的循环中判定失败但即便如此我们仍然遍历了范围内的每一个数。对于大范围这个遍历本身开销就很大。质数判断函数被频繁调用即使一个数通过了数字检查isPrime函数内部的循环for (int i 2; i * i n; i)对于一个大数来说计算量依然可观。虽然我们用了平方根优化但调用次数太多。在竞赛中这种暴力法很可能导致超时TLE。我们需要更聪明的策略。3. 高效求解“纯质数”的两种进阶思路既然暴力枚举所有数不行我们就要从“纯质数”的定义出发寻找更高效的生成或筛选方法。3.1 思路一DFS构造法我们注意到“纯质数”的每一位只能是{2,3,5,7}中的一个。那么我们可以主动用这些数字来“构造”可能的候选数而不是被动地检查每一个数。这本质上是一个深度优先搜索DFS生成所有由{2,3,5,7}组成的数字的问题然后再从中筛选出质数。算法步骤从一位数开始每一位有4种选择2,3,5,7。通过DFS递归地生成所有不超过上限N的、由这些数字组成的数。例如从空开始第一次递归可以生成2,3,5,7以2开头下一次递归可以生成22,23,25,27以此类推。每生成一个数num就判断num是否大于1且是质数isPrime(num)。如果是则计入答案。代码实现要点#include iostream #include vector using namespace std; int limit 20210605; // 题目给定的上限 int count 0; int primeDigits[4] {2, 3, 5, 7}; // 判断质数的函数同上略 bool isPrime(int n) { ... } void dfs(long long currentNum) { if (currentNum limit) return; // 超过上限剪枝 if (currentNum 1 isPrime(currentNum)) { count; // 找到纯质数 } for (int i 0; i 4; i) { long long nextNum currentNum * 10 primeDigits[i]; if (nextNum limit) { dfs(nextNum); } } } int main() { // 注意一位数的纯质数就是2,3,5,7本身我们从0开始DFS在递归中判断 // 也可以直接从2,3,5,7这四个一位数开始DFS逻辑更清晰 dfs(0); // 从0开始第一次递归会生成2,3,5,7 cout count endl; return 0; }这个方法的优势大幅减少候选数数量我们只生成了由{2,3,5,7}组成的数数量级从N例如千万级降到了4^1 4^2 ... 4^kk为位数对于上限202106058位数这个数量远小于一千万。质数判断次数少只对生成的候选数进行质数判断调用isPrime的次数极少。注意事项注意数据范围currentNum * 10可能导致溢出使用long long更安全。DFS的起点处理要小心。从0开始第一次递归生成一位数也可以写一个循环分别以2,3,5,7为起点进行DFS。3.2 思路二埃拉托斯特尼筛法Sieve of Eratosthenes结合数字检查另一种思路是先利用埃氏筛高效地筛选出给定范围内的所有质数然后遍历这些质数检查其每一位是否由质数数字组成。算法步骤创建一个大小为N1的布尔数组isPrime[]初始化所有元素为true。执行埃氏筛算法将非质数标记为false。遍历从2到N的所有数如果isPrime[i]为true即i是质数则检查i的每一位数字是否属于{2,3,5,7}。如果满足则计数。代码实现要点#include iostream #include vector #include cmath using namespace std; int main() { int N 20210605; vectorbool isPrime(N 1, true); isPrime[0] 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; } } } int purePrimeCount 0; for (int num 2; num N; num) { if (isPrime[num]) { int temp num; bool allDigitsPrime true; while (temp 0) { int digit temp % 10; if (digit ! 2 digit ! 3 digit ! 5 digit ! 7) { allDigitsPrime false; break; } temp / 10; } if (allDigitsPrime) { purePrimeCount; } } } cout purePrimeCount endl; return 0; }两种方法的对比与选择DFS构造法在“纯质数”密度较低的场景下因为约束强它生成的候选数极少因此isPrime判断次数最少通常更快。但它需要递归实现逻辑稍复杂。埃氏筛检查法思路直白先筛出所有质数再过滤。埃氏筛的时间复杂度接近O(N log log N)对于N2*10^7这个量级在现代计算机上是可以接受的大约在几百毫秒到一秒左右。它的优势是代码简单且一次性得到了所有质数如果题目有其他需求会更方便。实操心得在蓝桥杯竞赛环境中如果N在10^7量级两种方法通常都能通过。我个人更倾向于使用埃氏筛因为它逻辑简单不易写错且内存占用vectorbool经过特化每个元素只占1 bit对于这个范围也是可以接受的。如果N更大比如10^8DFS构造法的优势会更明显。4. “完全日期”问题日期遍历与数位平方和接下来我们看“完全日期”。题目定义一个日期的年、月、日组成的8位数或6位数如2021年4月5日可能是20210405将其每一位数字的平方相加得到一个和。如果这个和是一个完全平方数即和是某个整数的平方那么这个日期就是一个“完全日期”。题目通常要求统计一段日期区间内“完全日期”的个数。4.1 问题拆解与核心步骤解决这个问题可以分解为以下几个步骤日期遍历如何从起始日期一天一天地走到结束日期这是日期类问题的核心。数字提取与平方和计算给定一个日期如何生成对应的数字串并计算各位平方和完全平方数判断如何快速判断一个数是否为完全平方数4.2 日期遍历的稳健实现手动模拟日期的递增需要正确处理月份和年份的进位特别是闰年二月的情况。一个健壮的日期递增函数是基础。// 判断是否为闰年 bool isLeapYear(int year) { return (year % 4 0 year % 100 ! 0) || (year % 400 0); } // 获取某年某月的天数 int daysOfMonth(int year, int month) { int days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (month 2 isLeapYear(year)) { return 29; } return days[month]; } // 日期递增一天 void nextDay(int year, int month, int day) { day; if (day daysOfMonth(year, month)) { day 1; month; if (month 12) { month 1; year; } } }有了这个基础我们就可以用一个循环从起始日期遍历到结束日期。int startYear, startMonth, startDay; int endYear, endMonth, endDay; // 假设已初始化 int y startYear, m startMonth, d startDay; int count 0; while (!(y endYear m endMonth d endDay)) { // 检查当前日期(y,m,d)是否为完全日期 if (isPerfectDate(y, m, d)) { count; } nextDay(y, m, d); } // 别忘了检查最后一天 if (isPerfectDate(endYear, endMonth, endDay)) { count; }4.3 平方和计算与完全平方数判断对于日期20210405我们需要计算2^20^22^21^20^24^20^25^2。// 计算数字num的各位数字平方和 int digitSquareSum(int num) { int sum 0; while (num 0) { int digit num % 10; sum digit * digit; num / 10; } return sum; } // 判断一个数是否为完全平方数 bool isPerfectSquare(int n) { if (n 0) return false; int root (int)sqrt(n); // sqrt函数在cmath头文件中 return (root * root n); } // 判断一个日期是否为完全日期 bool isPerfectDate(int year, int month, int day) { int dateNumber year * 10000 month * 100 day; // 拼接成8位数 int sum digitSquareSum(dateNumber); return isPerfectSquare(sum); }踩坑提醒这里有一个极其重要的细节题目中“年、月、日组成的数字”的格式是什么是8位固定长度年份4位月份2位日2位还是可能为6位或7位如2021年4月5日是202104058位而2000年1月1日是200001018位但2000年1月10日也是200001108位实际上只要月份和日都用两位表示不足补零那么所有日期都是8位数。在编程时我们必须确保拼接出的数字是8位月份和日必须是两位数。例如2021年4月5日应该拼接成20210405而不是202145。上面的year*10000 month*100 day只有在month和day都是两位数时才正确。如果month4day5这样拼接出来是20210405吗不对2021*10000 4*100 5 20210000 400 5 20210405结果是正确的因为4*100400相当于在十位和个位留出了“04”的空间。但如果day15呢2021*10000 4*100 15 202100004001520210415也是正确的。所以这个算式是成立的前提是month和day作为整数参与计算它们本身的值就代表了其位置。更稳妥的做法是使用字符串格式化但整数运算在竞赛中更快。4.4 潜在的性能优化与边界思考对于日期遍历如果区间跨度很大比如几十年逐天遍历并计算平方和、开方判断计算量不小。但完全平方数的判断可以优化。平方和的范围一个8位数每位最大是9平方和最大是8 * 9^2 648。一个日期数字的平方和范围在0到648之间实际上不会为0因为日期数字不会全是0。预处理完全平方数表我们可以预先计算出1到648之间所有的完全平方数1,4,9,...,625等存入一个哈希集合如unordered_set或布尔数组中。这样isPerfectSquare函数就从需要开方运算变成了O(1)的查找操作。#include unordered_set #include cmath unordered_setint perfectSquares; void initPerfectSquares(int maxSum) { for (int i 1; i * i maxSum; i) { perfectSquares.insert(i * i); } } // 判断时 bool isPerfectSquareFast(int n) { return perfectSquares.find(n) ! perfectSquares.end(); }这个优化在竞赛中可能不是必需的因为648以内的开方计算很快但它体现了竞赛编程中“空间换时间”和“预处理”的常见思想。5. 代码整合与实战测试将两部分代码整合并针对蓝桥杯2021年国赛真题的具体要求进行实现。通常真题会给出明确的日期范围例如从2001年1月1日到2021年12月31日统计其中的“完全日期”个数。下面是一个完整的、经过优化的示例代码框架#include iostream #include vector #include cmath #include unordered_set using namespace std; // ---------- 日期相关函数 ---------- bool isLeapYear(int year) { return (year % 4 0 year % 100 ! 0) || (year % 400 0); } int daysOfMonth(int year, int month) { int days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (month 2 isLeapYear(year)) { return 29; } return days[month]; } void nextDay(int year, int month, int day) { day; if (day daysOfMonth(year, month)) { day 1; month; if (month 12) { month 1; year; } } } // ---------- 完全日期判断 ---------- int digitSquareSum(int num) { int sum 0; while (num 0) { int d num % 10; sum d * d; num / 10; } return sum; } // 预处理完全平方数表 (0-648) unordered_setint perfectSquares; void initPerfectSquares() { for (int i 0; i * i 648; i) { // 0也是完全平方数 perfectSquares.insert(i * i); } } bool isPerfectDate(int year, int month, int day) { int dateNum year * 10000 month * 100 day; int sum digitSquareSum(dateNum); return perfectSquares.find(sum) ! perfectSquares.end(); } int main() { // 初始化完全平方数集合 initPerfectSquares(); // 定义日期范围 (根据题目要求修改) int startY 2001, startM 1, startD 1; int endY 2021, endM 12, endD 31; int y startY, m startM, d startD; int perfectDateCount 0; // 遍历日期 while (!(y endY m endM d endD)) { if (isPerfectDate(y, m, d)) { perfectDateCount; } nextDay(y, m, d); } // 检查最后一天 if (isPerfectDate(endY, endM, endD)) { perfectDateCount; } cout 完全日期的个数为: perfectDateCount endl; return 0; }运行这段代码我们可以得到在2001-01-01到2021-12-31这个区间内“完全日期”的数量。根据实际计算这个结果是977。你可以自己运行验证一下。6. 举一反三从真题到通用解题能力通过这两道题我们可以总结出应对蓝桥杯乃至其他算法竞赛中类似问题的通用思路精确理解题意抓住约束条件“纯质数”的“纯”字是关键它包含了数字本身和数字位两个维度的质数约束。“完全日期”的关键是“完全平方数”需要准确进行数位分离和平方和计算。评估数据范围选择合适算法面对“纯质数”的上限如20210605暴力枚举所有数进行双重判断不可行必须利用条件进行剪枝DFS构造或使用高效筛法埃氏筛。这是竞赛编程的基本素养。掌握基础组件熟练实现质数判断、闰年判断、日期递推、数位分离、平方和计算、完全平方数判断这些都是基础的工具函数。在平时练习中就要做到能快速、准确、无Bug地写出这些代码。注意细节与边界日期拼接时月份和日的位数问题、循环的起始和终止条件是否包含最后一天、质数判断中1和0的处理、DFS中的溢出问题等。这些细节往往决定成败。思考优化空间在保证正确性的前提下思考是否有更优的算法如DFS vs 筛法、是否有预处理的可能如完全平方数表、是否有更快的判断方法如用乘法代替开方。即使对于简单题这种思考也能锻炼你的优化能力。最后关于“纯质数”的答案根据DFS或埃氏筛法计算在1到20210605范围内纯质数的个数是1903。你可以用上面提供的任一方法进行验证。把这些题目吃透不仅仅是得到答案更重要的是掌握背后的问题分析方法和代码实现技巧这才是备赛和提升编程能力的正道。