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^k（k为位数），对于上限20210605（8位数），这个数量远小于一千万。 - 质数判断次数少：只对生成的候选数进行质数判断，调用
isPrime的次数极少。
注意事项：
- 注意数据范围，
currentNum * 10可能导致溢出，使用long long更安全。 - DFS的起点处理要小心。从0开始，第一次递归生成一位数；也可以写一个循环，分别以2,3,5,7为起点进行DFS。
3.2 思路二：埃拉托斯特尼筛法（Sieve of Eratosthenes）结合数字检查
另一种思路是，先利用埃氏筛高效地筛选出给定范围内的所有质数，然后遍历这些质数，检查其每一位是否由质数数字组成。
算法步骤：
- 创建一个大小为
N+1的布尔数组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; vector<bool> 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)，对于N=2*10^7这个量级，在现代计算机上是可以接受的（大约在几百毫秒到一秒左右）。它的优势是代码简单，且一次性得到了所有质数，如果题目有其他需求会更方便。
实操心得：在蓝桥杯竞赛环境中，如果N在10^7量级，两种方法通常都能通过。我个人更倾向于使用埃氏筛，因为它逻辑简单，不易写错，且内存占用（
vector<bool>经过特化，每个元素只占1 bit）对于这个范围也是可以接受的。如果N更大（比如10^8），DFS构造法的优势会更明显。
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^2+0^2+2^2+1^2+0^2+4^2+0^2+5^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日是20210405，8位；而2000年1月1日是20000101，8位；但2000年1月10日也是20000110，8位）？实际上，只要月份和日都用两位表示（不足补零），那么所有日期都是8位数。在编程时，我们必须确保拼接出的数字是8位，月份和日必须是两位数。例如，2021年4月5日应该拼接成20210405，而不是202145。上面的
year*10000 + month*100 + day只有在month和day都是两位数时才正确。如果month=4，day=5，这样拼接出来是20210405吗？不对，2021*10000 + 4*100 + 5 = 20210000 + 400 + 5 = 20210405，结果是正确的，因为4*100=400，相当于在十位和个位留出了“04”的空间。但如果day=15呢？2021*10000 + 4*100 + 15 = 20210000+400+15=20210415，也是正确的。所以这个算式是成立的，前提是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_set<int> 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_set<int> 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。你可以用上面提供的任一方法进行验证。把这些题目吃透，不仅仅是得到答案，更重要的是掌握背后的问题分析方法和代码实现技巧，这才是备赛和提升编程能力的正道。
