1. 项目概述与核心思路拆解最近在复盘蓝桥杯2021年国赛的真题其中“纯质数”和“完全日期”这两道题很有意思它们不像一些复杂的图论或动态规划题那样让人望而生畏但恰恰是这种基础题最能考验一个选手对算法基本功和编程细节的掌握程度。很多新手觉得这类题简单上手就写结果要么超时要么漏掉各种边界条件最后丢分丢得不明不白。今天我就结合这两道国赛真题把里面涉及到的质数判断、日期处理、数位分解这些核心算法点以及C实现中的那些“坑”给大家掰开揉碎了讲清楚。我的目标不只是让你AC这两道题更是让你掌握解决这一类问题的通用方法和严谨思维。“纯质数”这道题要求我们在一个很大的范围比如1到20210605内找出那些本身是质数并且它的每一位数字也都是质数的数。听起来规则很简单对吧但这里暗藏了两个关键点一是高效判断大范围内的质数你不能对每个数都从2到sqrt(n)去试除那肯定超时二是如何优雅地分解一个数的每一位并进行判断。“完全日期”则是给定一个日期区间判断日期的年月日各位数字之和的平方根是否为整数。这题考验的是对日期模拟的熟练度包括闰年的判断、月份天数的处理以及如何高效地遍历日期。这两道题合在一起几乎覆盖了竞赛中基础数学和模拟类问题的核心考点。下面我们就先深入“纯质数”的腹地看看如何用高效的方法筛出我们需要的数。2. 纯质数高效筛法与数位处理的结合2.1 问题重述与暴力法的陷阱题目要求计算1到N例如20210605之间有多少个“纯质数”。纯质数需要满足两个条件它本身是一个质数。它的每一位数字十进制表示下也都是质数注意数字0、1、4、6、8、9都不是质数只有2、3、5、7是质数。最直观的想法就是写一个isPrime函数判断质数再写一个isPure函数判断每一位数字然后从1循环到N。我们来算笔账判断一个数n是否为质数最朴素的试除法需要循环到sqrt(n)时间复杂度是O(sqrt(n))。对于N20210605最坏情况下每个数都判断总计算量巨大必然超时。这是第一个陷阱——算法效率。第二个陷阱在于数位判断的逻辑。很多人会先判断数位再判断整体以为能提前剪枝。但顺序很重要如果一个数本身就不是质数我们根本不需要去分解它的数位。所以更优的策略是先判断这个数是不是质数如果不是直接跳过如果是再分解数位判断每一位。但即便如此对于每个质数我们还是要做一次sqrt(n)的试除当N很大时质数的数量也不少大约N/ln(N)计算量依然可观。所以我们需要更高效的方法。2.2 核心武器埃拉托斯特尼筛法埃氏筛对付大规模范围内的质数判断标准答案是“筛法”。埃氏筛的思想非常巧妙假设我们要找出所有小于等于N的质数。首先列出从2到N的所有整数。然后从最小的质数2开始划去列表中所有2的倍数除了2本身。接着找到下一个未被划去的数它一定是质数这里是3划去所有3的倍数。重复这个过程直到处理完所有小于等于sqrt(N)的数。剩下的未被划去的数就都是质数。为什么只需要筛到sqrt(N)呢因为对于任何合数n它必然有一个小于等于sqrt(n)的质因子。所以我们用小于等于sqrt(N)的质数去筛就足以把所有的合数都标记出来了。在代码中我们通常用一个布尔数组isPrime来标记isPrime[i] true表示i是质数。初始化时假设所有数都是质数然后把0和1设为false。接着从2开始循环到sqrt(N)如果当前数i是质数那么就把从ii开始每次增加i的所有倍数都标记为合数即isPrime[j] false。这里从ii开始是因为更小的倍数如2i, 3i, ..., (i-1)*i已经被之前更小的质数2, 3, ..., i-1筛过了。#include vector #include cmath using namespace std; vectorbool sieveOfEratosthenes(int n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; // 0和1不是质数 int sqrtN sqrt(n); for (int i 2; i sqrtN; i) { if (isPrime[i]) { // 从i*i开始标记避免重复标记 for (int j i * i; j n; j i) { isPrime[j] false; } } } return isPrime; }注意这里有一个经典的性能陷阱和内存考量。当N非常大比如上亿时vectorbool在内存优化上比较特殊每个元素只占1 bit但访问可能稍慢。如果追求极致速度且内存充足可以考虑用vectorchar或bitset。另外内层循环j从i*i开始如果i*i可能溢出int范围当N很大时需要将j的类型改为long long。在本题N20210605的范围内int是安全的。2.3 数位分解与质数数字判断有了质数表我们可以快速判断任意一个数是否为质数。接下来对于是质数的数我们需要分解它的每一位数字。这里我推荐使用while循环和取模运算这是最清晰高效的方法。bool isPurePrime(int num, const vectorbool isPrime) { // 首先这个数本身必须是质数 if (!isPrime[num]) { return false; } // 分解每一位数字进行判断 int temp num; while (temp 0) { int digit temp % 10; // 获取个位数 // 判断该数字是否为质数数字只有2,3,5,7是质数 if (digit ! 2 digit ! 3 digit ! 5 digit ! 7) { return false; } temp / 10; // 去掉个位数 } return true; }这里有几个细节需要注意数字0的处理如果原数num中包含0那么digit会在某次为0。而0不是质数所以函数会返回false。这符合题意。单独处理数字本身我们先判断num本身是否为质数如果不是直接返回避免了不必要的数位分解。质数数字集合一位数的质数只有2,3,5,7。所以判断条件很直接。注意1不是质数9也不是质数。2.4 整合与优化从暴力到高效现在我们把筛法和数位判断结合起来。主逻辑就非常清晰了使用埃氏筛预处理出从1到N的所有质数标记。从2开始循环到N注意1不是质数直接从2开始。对于每个数i先用质数表检查isPrime[i]如果为真再调用isPurePrime(i, isPrime)判断。统计满足条件的数的个数。#include iostream #include vector #include cmath using namespace std; int main() { int N 20210605; vectorbool isPrime sieveOfEratosthenes(N); int count 0; for (int i 2; i N; i) { if (isPurePrime(i, isPrime)) { count; // 如果需要输出具体的纯质数可以在这里打印 i // cout i endl; } } cout 纯质数的个数为: count endl; return 0; }实测与心得对于N20210605使用上述优化的埃氏筛预处理时间在普通家用PC上不到1秒后续的遍历判断也很快。如果使用最开始的暴力试除法估计几分钟都跑不完。这里的关键在于预处理思想——将大量查询中公共的、耗时的计算质数判断提前一次性完成后续每个查询都是O(1)的时间复杂度。这是竞赛中优化时间复杂度的常用手段。3. 完全日期日期模拟与数位求和的技巧3.1 问题解析与日期遍历策略“完全日期”题目通常描述为给定一个日期区间例如2001年1月1日到2021年12月31日我们需要找出其中有多少个日期其年、月、日各位数字之和是一个完全平方数。例如日期2021-06-05各位数字之和为2021060516而16是4的平方所以它是一个“完全日期”。解决这个问题的核心在于如何正确地、高效地遍历给定日期区间内的每一天。这里有两个主流方法日期类库法使用C11的chrono或C语言的ctime库利用tm结构体和mktime函数进行日期的加减。这种方法不易出错但需要熟悉相关库函数且可能在某些竞赛环境中受限。手动模拟法自己编写代码处理年、月、日的进位。这种方法更底层更能体现算法功底也是竞赛中的常见考点。我们重点讲解这种方法。手动模拟的关键在于正确处理每个月的天数特别是闰年二月的变化。我们的遍历框架通常是一个while循环从起始日期开始每次增加一天直到超过结束日期。3.2 核心组件月份天数与闰年判断这是日期题最经典的“坑点”必须熟练掌握。闰年判断规则年份满足以下条件之一即为闰年。能被400整除。能被4整除但不能被100整除。用C逻辑表达就是(year % 400 0) || (year % 4 0 year % 100 ! 0)月份天数我们用一个数组monthDays来存储平年每个月的天数。二月的天数需要根据是否闰年动态判断。// 平年每月天数索引1-12对应1月到12月索引0不用 int monthDays[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 判断闰年的函数 bool isLeapYear(int year) { return (year % 400 0) || (year % 4 0 year % 100 ! 0); } // 获取某年某月的天数 int getDaysOfMonth(int year, int month) { if (month 2) { return isLeapYear(year) ? 29 : 28; } else { return monthDays[month]; } }实操心得monthDays数组的大小设为13并使下标1对应1月这样更符合人类的直觉避免了下标转换的思维负担。虽然浪费了一个monthDays[0]的空间但在这种问题中代码清晰远比那一点内存重要。3.3 日期遍历与数位求和实现有了上面的工具函数我们就可以构建日期遍历器了。思路是定义年、月、日变量然后在一个循环中每次将日加1如果日超过了当前年月的天数则日重置为1月加1如果月超过了12则月重置为1年加1。循环的终止条件是日期超过给定的结束日期。在循环的每一步我们计算当前日期的数位和并判断其是否为完全平方数。数位求和我们需要将年、月、日的每一位数字相加。注意月和日可能是个位数如“2021-1-5”在求和时1和5应该作为独立的数字“1”和“5”加入而不是作为“01”和“05”的“0”和“1”、“0”和“5”。所以安全的做法是对年、月、日这三个数分别进行数位分解。// 计算一个整数的各位数字之和 int digitSum(int num) { int sum 0; while (num 0) { sum num % 10; num / 10; } return sum; } // 判断一个数是否为完全平方数 bool isPerfectSquare(int num) { if (num 0) return false; int root sqrt(num); return root * root num; }主遍历逻辑int countPerfectDates(int startYear, int startMonth, int startDay, int endYear, int endMonth, int endDay) { int year startYear, month startMonth, day startDay; int count 0; // 将结束日期转换为一个可比较的整数方便循环终止判断 // 更严谨的做法是写一个日期比较函数这里用整数简化 // 我们使用循环内直接比较年月日 while (!(year endYear || (year endYear month endMonth) || (year endYear month endMonth day endDay))) { // 计算当前日期的数位和 int totalSum digitSum(year) digitSum(month) digitSum(day); // 判断是否为完全平方数 if (isPerfectSquare(totalSum)) { count; // 可以打印出完全日期进行验证 // printf(%04d-%02d-%02d, sum%d\n, year, month, day, totalSum); } // 日期增加一天 day; if (day getDaysOfMonth(year, month)) { day 1; month; if (month 12) { month 1; year; } } } return count; }边界情况处理循环的终止条件需要小心处理。上面的while循环条件判断的是“当前日期是否还没有超过结束日期”。只要当前日期小于等于结束日期就继续处理。注意这里包含了结束日期当天。如果你需要包含结束日期这个逻辑是正确的。循环内部的“下一天”逻辑保证了最后一天会被正确处理。3.4 效率分析与潜在优化对于跨度几十年的日期遍历循环次数最多也就几万次365*20 ≈ 7300对于现代计算机来说完全是瞬间完成所以时间复杂度不是问题。关键在于代码的正确性和健壮性。一个常见的优化点是完全平方数的判断。我们使用了sqrt函数它返回浮点数然后取整再平方看是否等于原数。这种方法对于整数范围是可靠的。也可以预先计算出一个范围内日期数位和最大不会超过9*872因为年月日最多8位数字的所有完全平方数1,4,9,16,25,36,49,64,81然后用哈希集合来查找这样判断就是O(1)。但对于本题直接使用sqrt足够简洁高效。踩坑记录我曾经在写日期遍历时把day和月份、年份的进位逻辑写反了。应该是先判断加一天后是否溢出再进行进位。如果先day再判断day getDaysOfMonth(...)逻辑是清晰的。另一种写法是先判断day getDaysOfMonth(...)如果是则下一天是下个月1号。两种逻辑都要保证覆盖月末、年末的情况。务必自己用几个临界日期如2000-12-31 2004-02-28/29测试一下。4. 代码整合与测试验证将“纯质数”和“完全日期”的解决方案整合到一个程序中或者分别验证是最后的步骤。这里给出一个完整的示例框架并讨论如何验证结果的正确性。4.1 完整代码框架#include iostream #include vector #include cmath using namespace std; // ---------- 纯质数部分 ---------- vectorbool sieveOfEratosthenes(int n) { vectorbool isPrime(n 1, true); if (n 0) isPrime[0] false; if (n 1) isPrime[1] false; int sqrtN sqrt(n); for (int i 2; i sqrtN; i) { if (isPrime[i]) { // 注意防止 i*i 溢出使用 long long for (long long j (long long)i * i; j n; j i) { isPrime[j] false; } } } return isPrime; } bool isPurePrime(int num, const vectorbool isPrime) { if (num 2 || !isPrime[num]) return false; int temp num; while (temp 0) { int digit temp % 10; if (digit ! 2 digit ! 3 digit ! 5 digit ! 7) { return false; } temp / 10; } return true; } void solvePurePrime() { int N 20210605; cout 计算 1 到 N 之间的纯质数... endl; vectorbool isPrime sieveOfEratosthenes(N); int count 0; for (int i 2; i N; i) { if (isPurePrime(i, isPrime)) { count; } } cout 纯质数的个数为: count endl; } // ---------- 完全日期部分 ---------- bool isLeapYear(int year) { return (year % 400 0) || (year % 4 0 year % 100 ! 0); } int getDaysOfMonth(int year, int month) { static int monthDays[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (month 2) { return isLeapYear(year) ? 29 : 28; } return monthDays[month]; } int digitSum(int num) { int sum 0; while (num 0) { sum num % 10; num / 10; } return sum; } bool isPerfectSquare(int num) { int root sqrt(num); return root * root num; } void solvePerfectDate() { int startY 2001, startM 1, startD 1; int endY 2021, endM 12, endD 31; cout \n计算 startY - startM - startD 到 endY - endM - endD 之间的完全日期... endl; int y startY, m startM, d startD; int count 0; while (true) { // 先判断是否超过结束日期 if (y endY || (y endY m endM) || (y endY m endM d endD)) { break; } int totalSum digitSum(y) digitSum(m) digitSum(d); if (isPerfectSquare(totalSum)) { count; // 输出找到的完全日期便于验证 // printf(%04d-%02d-%02d (sum%d)\n, y, m, d, totalSum); } // 日期加一天 d; if (d getDaysOfMonth(y, m)) { d 1; m; if (m 12) { m 1; y; } } } cout 完全日期的个数为: count endl; } int main() { solvePurePrime(); solvePerfectDate(); return 0; }4.2 测试验证与常见错误排查写完代码不等于万事大吉必须进行测试。对于纯质数小范围验证将N设为一个小值比如20手动列出所有纯质数2,3,5,7,23。运行程序看结果是否匹配。边界测试检查数字0和1是否被正确排除。检查包含数字0、1、4、6、8、9的质数如19, 41是否被正确过滤。性能测试将N设回题目要求的20210605观察程序运行时间。如果超过几秒可能需要检查筛法实现是否有误比如内层循环的起始值或步长。对于完全日期单日测试手动计算几个已知日期如2021-06-05和为16是完全平方数修改程序只判断这一天看结果是否正确。短区间测试测试一个很短的区间比如2000-02-28到2000-03-02手动计算这个区间内的完全日期与程序输出对比。闰年测试确保在2000-02-28、2000-02-29、2000-03-01的过渡上日期递增逻辑正确并且2000-02-29被正确识别为有效日期。年末月初测试测试2000-12-31到2001-01-01的过渡。常见错误速查表问题现象可能原因排查方法纯质数结果偏少筛法标记错误误将质数标记为合数检查内层筛循环的起始值是否为i*i步长是否为i。检查isPrime数组初始化是否正确。纯质数结果偏多数位判断逻辑有误漏掉了非质数数字检查isPurePrime函数中对digit的判断条件是否只允许2,3,5,7。完全日期结果为0日期遍历循环没有执行或终止条件错误检查起始日期和终止日期的赋值检查while循环的终止条件逻辑。用cout打印循环第一天的日期和数位和。完全日期漏掉最后一天循环终止条件判断是“大于”结束日期导致最后一天未被处理将终止条件改为“大于”并在循环开始时就处理当前日期。或者使用do...while循环。二月天数错误闰年判断函数isLeapYear逻辑错误用几个年份测试2000闰、1900平、2004闰、2100平。数位和计算错误digitSum函数对个位数处理有误或对月、日分解时未考虑前导零确保digitSum对单个数字如5返回5。在求和时是对year,month,day这三个整数分别调用digitSum而不是将它们拼接成字符串。个人调试技巧在编写这类模拟题时我习惯在关键步骤后添加临时打印语句。比如在日期遍历循环里先打印出y, m, d和计算出的totalSum运行一个小范围区间肉眼核对。确认逻辑无误后再注释掉打印语句。对于筛法可以输出前100个质数与已知的质数表对比。这种“肉眼调试法”对于逻辑复杂的题目非常有效。5. 算法扩展与举一反三通过这两道题我们巩固了质数筛法和日期模拟这两个基础但重要的算法模块。但学习不能止步于AC更重要的是掌握其变体和应用场景。5.1 质数筛法的进阶欧拉筛线性筛埃氏筛的时间复杂度是O(n log log n)已经非常高效。但它存在一个小的瑕疵有些合数会被多个质数重复标记例如6会被2和3各标记一次。欧拉筛也叫线性筛通过保证每个合数只被它的最小质因子筛掉将时间复杂度降到了严格的O(n)。这在N极大比如10^7以上时会有细微优势并且它能同时得到每个数的最小质因子这个信息在某些更复杂的数论题中很有用。欧拉筛的核心思想是用一个数组isPrime标记质数同时用一个数组prime记录找到的质数列表。对于每个数i从2到N如果isPrime[i]为真则把i加入质数表。然后遍历当前质数表prime中的每个质数p将i * p标记为合数。关键点在于如果p能整除i那么在标记完i * p后就应该break。因为p是i的因子那么对于i * p来说p就是它的最小质因子。对于后续更大的质数pi * p的最小质因子应该是p而不是p所以应该留到后面当i增长到某个更大的值i使得i * p等于这个数时再由p来筛掉这样就保证了每个合数只被筛一次。vectorbool linearSieve(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; }对于蓝桥杯这类竞赛埃氏筛通常足够用了。但了解欧拉筛能让你在面试或者遇到更刁钻的问题时更有底气。5.2 日期问题的常见变体日期模拟题变化多端但核心离不开闰年判断和月份天数。这里列举几个常见变体你可以尝试用我们上面的框架来解决计算两个日期之间的天数差比如计算从1900年1月1日到给定日期经过了多少天。这需要你累加经过的每一年的天数平年365闰年366或者更巧妙地计算每个日期距离某个基准日如0000-01-01的天数然后相减。给定年月打印月历首先计算出该月1号是星期几需要知道一个基准日比如1900年1月1日是星期一然后根据天数打印出格式化的日历。判断日期是星期几有专门的公式如蔡勒公式也可以通过计算与某个已知星期几的日期的天数差来推算。节假日计算比如计算某年的母亲节五月的第二个星期日、感恩节十一月的第四个星期四等这需要在遍历日期的同时判断星期几。解决这些问题的通用步骤是先抽象出“下一天”的函数然后基于此实现任何复杂的日期计算和遍历。把“日期”当成一个可以自增的对象很多问题就简化成了循环和条件判断。5.3 数位处理的其他应用场景数位分解%10和/10是处理数字的基本功除了求和外还有数字反转如将123变成321。判断回文数将数字反转后与原数比较。数位DP动态规划解决诸如“在区间[A, B]内有多少个数满足其数位之和是S”这类问题这是竞赛中的高级考点其基础正是数位分解和状态表示。例如判断一个数是否为回文数bool isPalindrome(int x) { if (x 0) return false; // 负数不是回文数 int reversed 0, original x; while (x 0) { reversed reversed * 10 x % 10; x / 10; } return original reversed; }把“纯质数”和“完全日期”这两道题吃透其价值远不止于得到两个答案。它们像两个精致的样本展示了如何将基础算法筛法、模拟与具体问题数位性质、日期规则相结合。在平时练习时多问自己几个“为什么”为什么筛法要从i*i开始为什么闰年判断规则那么定如果题目规则变了比如纯质数的定义改为包含数字‘1’我的代码哪些地方需要改通过这样的思考你面对新题时拆解和构建解决方案的能力才会真正提升。编程竞赛尤其是蓝桥杯这种偏重基础和思维的比赛扎实的基本功和清晰的逻辑永远是通往高分的捷径。