1. 约数从数学概念到程序实现的核心解析约数或者叫因数这个概念我们小学就学过。一个整数a能被另一个整数b整除我们就说b是a的约数。听起来简单吧但就是这个简单的概念在编程尤其是算法竞赛和底层系统优化里扮演着极其关键的角色。无论是判断一个数是否为质数、求最大公约数GCD来简化分数还是解决一些看似复杂的数论问题比如“完全数”、“亲和数”甚至是RSA加密算法的基础都离不开对约数的高效计算和深入理解。在C的世界里处理约数不仅仅是数学问题更是对程序效率的极致考验。一个新手可能会写一个从1遍历到n的循环来找出所有约数这在n很小的时候没问题。但当n是一个十几位的大整数时这种暴力方法的耗时将是灾难性的。这就引出了我们讨论的核心如何利用数学性质在C中优雅且高效地处理约数相关的问题。本文将从一个C开发者的实战角度彻底拆解约数的求法、应用以及那些容易踩坑的细节目标是让你看完之后不仅能写出代码更能理解背后的“为什么”在面试或实际项目中遇到相关问题能游刃有余。2. 约数基础与高效求解算法2.1 约数的定义与基本性质在深入代码之前我们必须夯实数学基础。对于整数a和bb ≠ 0如果存在整数k使得 a k × b那么b就是a的约数。例如12的约数有1, 2, 3, 4, 6, 12。这里有几个关键性质直接影响我们的算法设计成对出现如果d是n的约数那么n/d也一定是n的约数。比如6是12的约数那么12/62也是约数。这个性质是优化遍历范围的核心。平凡约数1和n本身总是n的约数。平方根特性对于任意一个约数对(d, n/d)其中较小的那个一定不大于√n。这是将算法复杂度从O(n)降低到O(√n)的理论依据。理解这些性质后我们就能明白最笨的从1到n的遍历方法其实做了大量重复且不必要的检查。2.2 试除法O(√n)复杂度求所有约数试除法是求一个数所有约数最常用且高效的方法直接利用了上述的平方根特性。基本思路我们只需要从1遍历到√n向下取整。对于每个能整除n的整数i我们就找到了两个约数i 和 n/i。需要特别注意处理完全平方数的情况避免将平方根重复加入约数列表两次。C实现与详细解析#include iostream #include vector #include algorithm #include cmath using namespace std; vectorint getDivisors(int n) { vectorint divisors; // 1. 遍历到平方根即可 for (int i 1; i sqrt(n); i) { // 注意这里i是int循环条件用i*i n更精确避免浮点数误差 if (n % i 0) { divisors.push_back(i); // 找到较小的约数i if (i ! n / i) { // 关键避免重复添加平方根 divisors.push_back(n / i); // 添加对应的约数n/i } } } // 2. 排序使约数序列有序可选但通常需要 sort(divisors.begin(), divisors.end()); return divisors; } int main() { int num 36; vectorint divs getDivisors(num); cout Divisors of num are: ; for (int d : divs) cout d ; cout endl; return 0; }代码细节与避坑指南循环条件的选择i sqrt(n)在概念上清晰但每次循环都计算sqrt(n)一个相对耗时的浮点运算并不高效。更优的做法是使用i * i n作为条件。但要注意i*i可能溢出当n接近int类型最大值时i*i会溢出变成负数导致循环提前错误结束。对于大整数可以使用long long类型或者用i n / i作为条件这是最安全且高效的方式。排序的必要性由于我们是一对小一对大地插入约数先i后n/i得到的向量是无序的。sort函数调用增加了O(d log d)的复杂度其中d是约数个数。对于需要有序约数的场景这是必要的。如果后续使用不要求顺序可以省略排序以提升性能。边界情况n0时任何非零数都是0的约数因为0除以任何数等于0但通常题目中会规定正整数。n1时约数只有1。我们的代码能正确处理这些情况吗对于n1sqrt(1)1循环会执行一次i1n%i0插入1然后判断1 ! 1/1不1 ! 1为假所以不会重复插入。正确。注意sqrt(n)返回浮点数在与整数i比较时可能存在精度问题。例如对于某个很大的完全平方数sqrt(n)的结果可能略微小于理论整数平方根。使用i n / i是整数运算绝对精确是推荐做法。2.3 约数个数与约数和的公式及计算有时我们不需要列出所有约数只需要知道约数的个数或者所有约数的和。利用数论中的算术基本定理我们可以高效计算。算术基本定理任何一个大于1的正整数n都可以唯一地分解为质因数的乘积。n p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是质数a1, a2, ..., ak是正整数。基于这个分解约数个数公式d(n) (a1 1) * (a2 1) * ... * (ak 1)原理每个质因数pi的指数可以从0取到ai共有(ai1)种选择。所有选择独立相乘就得到了所有可能的约数数量。举例180 2^2 * 3^2 * 5^1。约数个数 (21)(21)(11) 332 18。约数和公式σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)原理这是等比数列求和公式的应用。对于质因数pi其贡献的因子和是1 pi pi^2 ... pi^ai (pi^(ai1)-1)/(pi-1)。所有质因数贡献相乘即为总和。举例180 2^2 * 3^2 * 5^1。约数和 ((2^3-1)/(2-1)) * ((3^3-1)/(3-1)) * ((5^2-1)/(5-1)) (7/1)(26/2)(24/4) 7136 546。C实现质因数分解与计算#include iostream #include map #include cmath using namespace std; // 辅助函数快速幂计算 a^b long long quickPow(long long a, int b) { long long res 1; while (b) { if (b 1) res * a; a * a; b 1; } return res; } pairint, long long getDivisorCountAndSum(int n) { int temp n; mapint, int primeFactors; // 存储质因数及其指数 // 质因数分解 for (int i 2; i temp / i; i) { // 试除法分解质因数 while (temp % i 0) { primeFactors[i]; temp / i; } } if (temp 1) primeFactors[temp]; // 处理最后剩余的质因数 // 计算约数个数和约数和 int count 1; long long sum 1; for (auto [p, a] : primeFactors) { count * (a 1); // 计算 (p^(a1)-1)/(p-1) long long numerator quickPow(p, a 1) - 1; long long denominator p - 1; sum * (numerator / denominator); // 这里确保整除 } return {count, sum}; } int main() { int num 180; auto [cnt, sum] getDivisorCountAndSum(num); cout Number of divisors of num : cnt endl; cout Sum of divisors of num : sum endl; return 0; }实操心得质因数分解的效率上述分解算法复杂度约为O(√n)。对于单个大数这已经不错。但如果需要对一个范围内的所有数进行预处理就需要更高效的筛法如欧拉筛来快速获取质因数。快速幂的必要性在计算约数和时p^(a1)可能非常大。直接使用pow函数浮点数版本会有精度损失使用循环乘会超时。因此快速幂算法是必备技能它能在O(log b)时间内计算a^b。数据类型选择约数和可能增长得非常快很容易超出int甚至long的范围。务必根据题目要求使用long long或高精度类型。3. 约数相关经典算法实战3.1 最大公约数与最小公倍数最大公约数Greatest Common Divisor, GCD和最小公倍数Least Common Multiple, LCM是约数概念最直接的应用。欧几里得算法辗转相除法计算GCD的经典算法基于原理gcd(a, b) gcd(b, a % b)。其时间复杂度为O(log min(a, b))效率极高。关系对于两个正整数a和b有a * b gcd(a, b) * lcm(a, b)。因此求LCM可以通过GCD间接得到lcm(a, b) a / gcd(a, b) * b。注意先除后乘避免中间结果溢出。C实现与工程细节#include iostream #include numeric // C17起std::gcd, std::lcm 已在标准库中 using namespace std; // 自定义实现递归版本清晰 int gcd_recursive(int a, int b) { return b 0 ? a : gcd_recursive(b, a % b); } // 自定义实现迭代版本高效无栈溢出风险 int gcd_iterative(int a, int b) { while (b ! 0) { int t a % b; a b; b t; } return a; } // 求最小公倍数 int lcm(int a, int b) { // 先除后乘是防止溢出的关键技巧 return a / gcd_iterative(a, b) * b; } int main() { int x 48, y 18; cout GCD( x , y ) [Custom] gcd_iterative(x, y) endl; cout GCD( x , y ) [std] std::gcd(x, y) endl; // C17 cout LCM( x , y ) lcm(x, y) endl; return 0; }注意事项负数处理GCD通常定义为正数。上述自定义实现对于负数输入结果可能为负。标准库的std::gcd返回非负结果。在实际应用中可以先取绝对值abs()。零的处理gcd(a, 0) |a|。我们的迭代版本能正确处理当b0时循环结束返回a。溢出问题在求LCM时a * b很可能溢出。所以务必使用a / gcd(a, b) * b这种先除后乘的写法这是算法竞赛和工程中的常见技巧。3.2 质数判定与约数的关系判断一个数n是否为质数本质就是看它是否有除了1和自身以外的正约数。最直接的想法是试除。朴素判定法遍历2到n-1看是否有数能整除n。复杂度O(n)。优化1只需遍历2到√n。复杂度O(√n)。优化2进一步除了2以外所有偶数都不是质数。可以先判断n是否为2然后只用在奇数范围内[3, √n]进行试除。复杂度O(√n/2)。C实现bool isPrime_naive(int n) { if (n 1) return false; for (int i 2; i n; i) if (n % i 0) return false; return true; } bool isPrime_sqrt(int n) { if (n 1) return false; for (int i 2; i n / i; i) if (n % i 0) return false; // 用 i n/i return true; } bool isPrime_optimized(int n) { if (n 1) return false; if (n 2) return true; if (n % 2 0) return false; // 排除偶数 for (int i 3; i n / i; i 2) if (n % i 0) return false; // 只检查奇数 return true; }更高级的算法对于极大的整数如几百位O(√n)的复杂度也不够。这时需要概率性素性测试算法如Miller-Rabin算法它基于数论定理可以在多项式时间内以极高的概率判断一个大数是否为质数广泛应用于密码学。3.3 筛法求范围内所有数的约数信息当问题不是求单个数的约数而是求一个区间内所有数的约数时比如“求1到N每个数的约数个数”如果对每个数单独用试除法总复杂度是O(N√N)对于N10^6就已经力不从心了。这时就需要筛法。其核心思想是“用约数去找倍数”而不是“用数去找约数”。埃拉托斯特尼筛法求质数是筛法的经典代表。类似的我们可以修改筛法来预处理每个数的约数信息。应用1用筛法求1~N每个数的约数个数思路初始化一个数组div_cnt[N1]全部为1因为1是每个数的约数。然后对于每个数i从2开始我们知道i是所有i, 2i, 3i, ...的约数。所以我们可以遍历i的倍数j让div_cnt[j]。但这样每个数会被它的每个约数标记一次总复杂度是O(N/1 N/2 ... N/N) ≈ O(N log N)效率很高。#include iostream #include vector using namespace std; vectorint getDivisorCountUpTo(int N) { vectorint div_cnt(N 1, 1); // 每个数至少有1个约数1 div_cnt[0] 0; // 0没有约数 for (int i 2; i N; i) { for (int j i; j N; j i) { div_cnt[j]; // i是j的约数 } } return div_cnt; } // 更高效的写法利用质因数分解公式通过筛法记录每个数的最小质因子可以线性O(N)求出每个数的约数个数。应用2用筛法求1~N每个数的约数和思路类似用一个数组div_sum[N1]初始化为1。对于每个数i将其加到所有它的倍数j的div_sum[j]上。vectorlong long getDivisorSumUpTo(int N) { vectorlong long div_sum(N 1, 1); div_sum[0] 0; for (int i 2; i N; i) { for (int j i; j N; j i) { div_sum[j] i; } } return div_sum; }筛法的优势一次O(N log N)的预处理后查询任意一个数的约数个数或和都是O(1)的。这在解决需要大量查询的问题时优势巨大。4. 约数在C项目中的典型应用与问题排查4.1 应用场景举例分数化简在实现分数类Fraction时分子分母同除以它们的最大公约数GCD即可得到最简分数。struct Fraction { long long num, den; void simplify() { long long g std::gcd(num, den); // C17 num / g; den / g; if (den 0) { num -num; den -den; } // 保证分母为正 } };周期性问题许多循环、模拟问题中周期长度往往是相关数字的最小公倍数LCM。例如多个齿轮同时转动回到初始位置的时间是它们周期的最小公倍数。完全数与亲和数判断完全数一个数等于它的所有真约数除了自身以外的约数之和。如6123。亲和数两个数其中一个数的所有真约数之和等于另一个数反之亦然。如(220, 284)。 判断这类数都需要高效计算约数和。加密算法基础RSA公钥加密算法的安全性基于大整数的质因数分解难题而密钥生成过程中大量用到求模逆元这又依赖于扩展欧几里得算法GCD算法的扩展。4.2 常见问题、陷阱与调试技巧问题1整数溢出这是数论问题中最常见的坑。即便输入在int范围内中间计算结果如乘法、幂运算也可能溢出。对策分析数据范围预估中间结果大小。默认使用long long64位进行计算特别是涉及乘法、求幂时。在求LCM时务必使用a / gcd(a, b) * b。对于更大的数需要使用高精度计算用数组或字符串模拟。问题2循环边界与精度陷阱for (int i 1; i sqrt(n); i)。sqrt(n)返回double对于完全平方数如n25sqrt(25)在计算机中可能是4.999999...导致i4.999为真i5时循环不执行漏掉了约数5。解决方案使用i * i n注意溢出或更安全的i n / i。问题3重复添加约数在试除法中对于完全平方数n当i等于sqrt(n)时i和n/i是同一个数。如果不加判断if (i ! n / i)就会在约数列表中添加两次。检查用完全平方数如3649测试你的getDivisors函数看输出是否正确。问题4算法复杂度估计错误新手容易写出O(n)的求约数循环当n很大时程序超时。调试对于输入规模大的题目先在本地用最大边界值测试运行时间。养成习惯看到“求约数”第一反应就应该是O(√n)的试除法或筛法。问题5特殊输入处理n0或n1明确题目定义。通常我们讨论的是正整数约数。0的约数定义有争议1只有1个约数。负数如果题目可能包含负数需要明确是否考虑负约数。通常可以先取绝对值处理再根据题意调整。调试技巧实录小数据测试用几个小例子如n1, 2, 6, 12, 16, 25手动计算预期结果与程序输出对比。打印中间变量在循环中打印i,n%i等值观察程序实际执行流程。边界测试用int最大值INT_MAX约21亿附近的数测试检查溢出和效率。使用标准库对照对于GCD可以用C17的std::gcd来验证自己实现的正确性。5. 性能优化与进阶话题5.1 从O(√n)到更优Pollard-Rho算法当n非常大比如10^18时即使是O(√n)的试除法也无法在短时间内完成质因数分解。这时就需要更高级的算法如Pollard-Rho算法。它是一种概率性算法用于快速找到大整数的一个非平凡因子即不是1和它本身的因子。其核心思想是利用生日悖论和Floyd判圈算法通过一个随机生成的函数序列来寻找n的因子。期望时间复杂度约为O(n^{1/4})对于大数分解是革命性的。不过其实现较为复杂涉及模运算、随机数生成和最大公约数计算。通常只在专门的数论库或应对极端情况时使用。5.2 预处理与查询的权衡在算法竞赛或高频查询的业务场景中我们需要在“预处理耗时”和“单次查询耗时”之间做权衡。场景A少量查询n很大- 对每个查询单独用试除法或高级算法。场景B大量查询Q次n在中等范围如N≤10^6- 使用筛法O(N log log N)预处理出所有数的约数列表/个数/和然后每次查询O(1)响应。总复杂度O(N log log N Q)远优于O(Q√N)。场景C需要频繁获取某个数的所有约数- 可以预处理出每个数的最小质因子然后在查询时利用质因数分解公式和递归方法在O(log n)时间内动态生成所有约数比存储所有约数列表更省空间。5.3 多线程与并发计算在极其追求性能的场合如科学计算求一个大数的所有约数可以被并行化。因为检查i和n/i是否能整除n是相互独立的。可以将区间[1, √n]分成若干段交给多个线程同时进行试除最后合并结果。但需要注意线程同步和负载均衡。对于质因数分解Pollard-Rho算法本身也有并行化的变种。6. 一个综合案例解决“因子求和”问题让我们用一个经典问题来串联所学知识“求一个正整数n的所有真约数之和”。问题分析真约数之和等于约数之和减去n本身。我们可以用两种方法方法A直接试除遍历1到√n累加约数对i和n/i最后减去n。时间复杂度O(√n)空间复杂度O(1)。方法B公式法先质因数分解再利用约数和公式计算σ(n)最后减去n。分解质因数最坏也是O(√n)但对于有很多小质因子的数分解很快。C实现对比#include iostream #include cmath using namespace std; // 方法A试除法直接求和 long long sumProperDivisors_direct(int n) { if (n 1) return 0; long long sum 0; for (int i 1; i n / i; i) { if (n % i 0) { sum i; if (i ! n / i i ! 1) { // 注意1和n本身这里我们求真约数不包含n sum n / i; } } } // 上面的循环当i1时加了1当in时不会进入因为in/i // 所以sum现在包含1。真约数之和是除了n以外的所有约数和所以就是当前的sum因为没加n // 但注意当i是n的平方根时我们只加了一次i。需要仔细处理。 // 更清晰的写法 sum 0; for (int i 1; i n / i; i) { if (n % i 0) { sum i; if (i ! n / i) { sum n / i; } } } return sum - n; // 总和减去自己得到真约数和 } // 方法B公式法需要质因数分解和快速幂 long long quickPow(long long a, int b) { long long res 1; while (b) { if (b 1) res * a; a * a; b 1; } return res; } long long sumProperDivisors_formula(int n) { int temp n; long long sum 1; for (int i 2; i temp / i; i) { if (temp % i 0) { int cnt 0; while (temp % i 0) { cnt; temp / i; } sum * (quickPow(i, cnt 1) - 1) / (i - 1); } } if (temp 1) { sum * (quickPow(temp, 2) - 1) / (temp - 1); } return sum - n; } int main() { int n 28; // 完全数28124714 cout Direct method: sumProperDivisors_direct(n) endl; cout Formula method: sumProperDivisors_formula(n) endl; // 验证 cout Is 28 a perfect number? (sumProperDivisors_direct(n) n ? Yes : No) endl; return 0; }选择建议对于单个查询两种方法复杂度相当。试除法代码更简单不易出错。如果需要多次查询不同n的约数和且n值较大公式法配合预处理的最小质因子筛可能会更有优势因为质因数分解可以很快。如果n非常大超过10^12试除法可能太慢而公式法中的质因数分解也会变慢可能需要Pollard-Rho算法。我个人在实际编码中对于int范围内的数更倾向于使用试除法因为它直白、不容易在边界条件上出错而且现代CPU执行O(√n)次循环对于n10^9也就约3万次迭代是瞬间完成的。代码的清晰度和可维护性往往是第一位的除非性能测试表明这里成了瓶颈。 C++高效计算约数：从试除法到筛法，原理与实战详解
1. 约数从数学概念到程序实现的核心解析约数或者叫因数这个概念我们小学就学过。一个整数a能被另一个整数b整除我们就说b是a的约数。听起来简单吧但就是这个简单的概念在编程尤其是算法竞赛和底层系统优化里扮演着极其关键的角色。无论是判断一个数是否为质数、求最大公约数GCD来简化分数还是解决一些看似复杂的数论问题比如“完全数”、“亲和数”甚至是RSA加密算法的基础都离不开对约数的高效计算和深入理解。在C的世界里处理约数不仅仅是数学问题更是对程序效率的极致考验。一个新手可能会写一个从1遍历到n的循环来找出所有约数这在n很小的时候没问题。但当n是一个十几位的大整数时这种暴力方法的耗时将是灾难性的。这就引出了我们讨论的核心如何利用数学性质在C中优雅且高效地处理约数相关的问题。本文将从一个C开发者的实战角度彻底拆解约数的求法、应用以及那些容易踩坑的细节目标是让你看完之后不仅能写出代码更能理解背后的“为什么”在面试或实际项目中遇到相关问题能游刃有余。2. 约数基础与高效求解算法2.1 约数的定义与基本性质在深入代码之前我们必须夯实数学基础。对于整数a和bb ≠ 0如果存在整数k使得 a k × b那么b就是a的约数。例如12的约数有1, 2, 3, 4, 6, 12。这里有几个关键性质直接影响我们的算法设计成对出现如果d是n的约数那么n/d也一定是n的约数。比如6是12的约数那么12/62也是约数。这个性质是优化遍历范围的核心。平凡约数1和n本身总是n的约数。平方根特性对于任意一个约数对(d, n/d)其中较小的那个一定不大于√n。这是将算法复杂度从O(n)降低到O(√n)的理论依据。理解这些性质后我们就能明白最笨的从1到n的遍历方法其实做了大量重复且不必要的检查。2.2 试除法O(√n)复杂度求所有约数试除法是求一个数所有约数最常用且高效的方法直接利用了上述的平方根特性。基本思路我们只需要从1遍历到√n向下取整。对于每个能整除n的整数i我们就找到了两个约数i 和 n/i。需要特别注意处理完全平方数的情况避免将平方根重复加入约数列表两次。C实现与详细解析#include iostream #include vector #include algorithm #include cmath using namespace std; vectorint getDivisors(int n) { vectorint divisors; // 1. 遍历到平方根即可 for (int i 1; i sqrt(n); i) { // 注意这里i是int循环条件用i*i n更精确避免浮点数误差 if (n % i 0) { divisors.push_back(i); // 找到较小的约数i if (i ! n / i) { // 关键避免重复添加平方根 divisors.push_back(n / i); // 添加对应的约数n/i } } } // 2. 排序使约数序列有序可选但通常需要 sort(divisors.begin(), divisors.end()); return divisors; } int main() { int num 36; vectorint divs getDivisors(num); cout Divisors of num are: ; for (int d : divs) cout d ; cout endl; return 0; }代码细节与避坑指南循环条件的选择i sqrt(n)在概念上清晰但每次循环都计算sqrt(n)一个相对耗时的浮点运算并不高效。更优的做法是使用i * i n作为条件。但要注意i*i可能溢出当n接近int类型最大值时i*i会溢出变成负数导致循环提前错误结束。对于大整数可以使用long long类型或者用i n / i作为条件这是最安全且高效的方式。排序的必要性由于我们是一对小一对大地插入约数先i后n/i得到的向量是无序的。sort函数调用增加了O(d log d)的复杂度其中d是约数个数。对于需要有序约数的场景这是必要的。如果后续使用不要求顺序可以省略排序以提升性能。边界情况n0时任何非零数都是0的约数因为0除以任何数等于0但通常题目中会规定正整数。n1时约数只有1。我们的代码能正确处理这些情况吗对于n1sqrt(1)1循环会执行一次i1n%i0插入1然后判断1 ! 1/1不1 ! 1为假所以不会重复插入。正确。注意sqrt(n)返回浮点数在与整数i比较时可能存在精度问题。例如对于某个很大的完全平方数sqrt(n)的结果可能略微小于理论整数平方根。使用i n / i是整数运算绝对精确是推荐做法。2.3 约数个数与约数和的公式及计算有时我们不需要列出所有约数只需要知道约数的个数或者所有约数的和。利用数论中的算术基本定理我们可以高效计算。算术基本定理任何一个大于1的正整数n都可以唯一地分解为质因数的乘积。n p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是质数a1, a2, ..., ak是正整数。基于这个分解约数个数公式d(n) (a1 1) * (a2 1) * ... * (ak 1)原理每个质因数pi的指数可以从0取到ai共有(ai1)种选择。所有选择独立相乘就得到了所有可能的约数数量。举例180 2^2 * 3^2 * 5^1。约数个数 (21)(21)(11) 332 18。约数和公式σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)原理这是等比数列求和公式的应用。对于质因数pi其贡献的因子和是1 pi pi^2 ... pi^ai (pi^(ai1)-1)/(pi-1)。所有质因数贡献相乘即为总和。举例180 2^2 * 3^2 * 5^1。约数和 ((2^3-1)/(2-1)) * ((3^3-1)/(3-1)) * ((5^2-1)/(5-1)) (7/1)(26/2)(24/4) 7136 546。C实现质因数分解与计算#include iostream #include map #include cmath using namespace std; // 辅助函数快速幂计算 a^b long long quickPow(long long a, int b) { long long res 1; while (b) { if (b 1) res * a; a * a; b 1; } return res; } pairint, long long getDivisorCountAndSum(int n) { int temp n; mapint, int primeFactors; // 存储质因数及其指数 // 质因数分解 for (int i 2; i temp / i; i) { // 试除法分解质因数 while (temp % i 0) { primeFactors[i]; temp / i; } } if (temp 1) primeFactors[temp]; // 处理最后剩余的质因数 // 计算约数个数和约数和 int count 1; long long sum 1; for (auto [p, a] : primeFactors) { count * (a 1); // 计算 (p^(a1)-1)/(p-1) long long numerator quickPow(p, a 1) - 1; long long denominator p - 1; sum * (numerator / denominator); // 这里确保整除 } return {count, sum}; } int main() { int num 180; auto [cnt, sum] getDivisorCountAndSum(num); cout Number of divisors of num : cnt endl; cout Sum of divisors of num : sum endl; return 0; }实操心得质因数分解的效率上述分解算法复杂度约为O(√n)。对于单个大数这已经不错。但如果需要对一个范围内的所有数进行预处理就需要更高效的筛法如欧拉筛来快速获取质因数。快速幂的必要性在计算约数和时p^(a1)可能非常大。直接使用pow函数浮点数版本会有精度损失使用循环乘会超时。因此快速幂算法是必备技能它能在O(log b)时间内计算a^b。数据类型选择约数和可能增长得非常快很容易超出int甚至long的范围。务必根据题目要求使用long long或高精度类型。3. 约数相关经典算法实战3.1 最大公约数与最小公倍数最大公约数Greatest Common Divisor, GCD和最小公倍数Least Common Multiple, LCM是约数概念最直接的应用。欧几里得算法辗转相除法计算GCD的经典算法基于原理gcd(a, b) gcd(b, a % b)。其时间复杂度为O(log min(a, b))效率极高。关系对于两个正整数a和b有a * b gcd(a, b) * lcm(a, b)。因此求LCM可以通过GCD间接得到lcm(a, b) a / gcd(a, b) * b。注意先除后乘避免中间结果溢出。C实现与工程细节#include iostream #include numeric // C17起std::gcd, std::lcm 已在标准库中 using namespace std; // 自定义实现递归版本清晰 int gcd_recursive(int a, int b) { return b 0 ? a : gcd_recursive(b, a % b); } // 自定义实现迭代版本高效无栈溢出风险 int gcd_iterative(int a, int b) { while (b ! 0) { int t a % b; a b; b t; } return a; } // 求最小公倍数 int lcm(int a, int b) { // 先除后乘是防止溢出的关键技巧 return a / gcd_iterative(a, b) * b; } int main() { int x 48, y 18; cout GCD( x , y ) [Custom] gcd_iterative(x, y) endl; cout GCD( x , y ) [std] std::gcd(x, y) endl; // C17 cout LCM( x , y ) lcm(x, y) endl; return 0; }注意事项负数处理GCD通常定义为正数。上述自定义实现对于负数输入结果可能为负。标准库的std::gcd返回非负结果。在实际应用中可以先取绝对值abs()。零的处理gcd(a, 0) |a|。我们的迭代版本能正确处理当b0时循环结束返回a。溢出问题在求LCM时a * b很可能溢出。所以务必使用a / gcd(a, b) * b这种先除后乘的写法这是算法竞赛和工程中的常见技巧。3.2 质数判定与约数的关系判断一个数n是否为质数本质就是看它是否有除了1和自身以外的正约数。最直接的想法是试除。朴素判定法遍历2到n-1看是否有数能整除n。复杂度O(n)。优化1只需遍历2到√n。复杂度O(√n)。优化2进一步除了2以外所有偶数都不是质数。可以先判断n是否为2然后只用在奇数范围内[3, √n]进行试除。复杂度O(√n/2)。C实现bool isPrime_naive(int n) { if (n 1) return false; for (int i 2; i n; i) if (n % i 0) return false; return true; } bool isPrime_sqrt(int n) { if (n 1) return false; for (int i 2; i n / i; i) if (n % i 0) return false; // 用 i n/i return true; } bool isPrime_optimized(int n) { if (n 1) return false; if (n 2) return true; if (n % 2 0) return false; // 排除偶数 for (int i 3; i n / i; i 2) if (n % i 0) return false; // 只检查奇数 return true; }更高级的算法对于极大的整数如几百位O(√n)的复杂度也不够。这时需要概率性素性测试算法如Miller-Rabin算法它基于数论定理可以在多项式时间内以极高的概率判断一个大数是否为质数广泛应用于密码学。3.3 筛法求范围内所有数的约数信息当问题不是求单个数的约数而是求一个区间内所有数的约数时比如“求1到N每个数的约数个数”如果对每个数单独用试除法总复杂度是O(N√N)对于N10^6就已经力不从心了。这时就需要筛法。其核心思想是“用约数去找倍数”而不是“用数去找约数”。埃拉托斯特尼筛法求质数是筛法的经典代表。类似的我们可以修改筛法来预处理每个数的约数信息。应用1用筛法求1~N每个数的约数个数思路初始化一个数组div_cnt[N1]全部为1因为1是每个数的约数。然后对于每个数i从2开始我们知道i是所有i, 2i, 3i, ...的约数。所以我们可以遍历i的倍数j让div_cnt[j]。但这样每个数会被它的每个约数标记一次总复杂度是O(N/1 N/2 ... N/N) ≈ O(N log N)效率很高。#include iostream #include vector using namespace std; vectorint getDivisorCountUpTo(int N) { vectorint div_cnt(N 1, 1); // 每个数至少有1个约数1 div_cnt[0] 0; // 0没有约数 for (int i 2; i N; i) { for (int j i; j N; j i) { div_cnt[j]; // i是j的约数 } } return div_cnt; } // 更高效的写法利用质因数分解公式通过筛法记录每个数的最小质因子可以线性O(N)求出每个数的约数个数。应用2用筛法求1~N每个数的约数和思路类似用一个数组div_sum[N1]初始化为1。对于每个数i将其加到所有它的倍数j的div_sum[j]上。vectorlong long getDivisorSumUpTo(int N) { vectorlong long div_sum(N 1, 1); div_sum[0] 0; for (int i 2; i N; i) { for (int j i; j N; j i) { div_sum[j] i; } } return div_sum; }筛法的优势一次O(N log N)的预处理后查询任意一个数的约数个数或和都是O(1)的。这在解决需要大量查询的问题时优势巨大。4. 约数在C项目中的典型应用与问题排查4.1 应用场景举例分数化简在实现分数类Fraction时分子分母同除以它们的最大公约数GCD即可得到最简分数。struct Fraction { long long num, den; void simplify() { long long g std::gcd(num, den); // C17 num / g; den / g; if (den 0) { num -num; den -den; } // 保证分母为正 } };周期性问题许多循环、模拟问题中周期长度往往是相关数字的最小公倍数LCM。例如多个齿轮同时转动回到初始位置的时间是它们周期的最小公倍数。完全数与亲和数判断完全数一个数等于它的所有真约数除了自身以外的约数之和。如6123。亲和数两个数其中一个数的所有真约数之和等于另一个数反之亦然。如(220, 284)。 判断这类数都需要高效计算约数和。加密算法基础RSA公钥加密算法的安全性基于大整数的质因数分解难题而密钥生成过程中大量用到求模逆元这又依赖于扩展欧几里得算法GCD算法的扩展。4.2 常见问题、陷阱与调试技巧问题1整数溢出这是数论问题中最常见的坑。即便输入在int范围内中间计算结果如乘法、幂运算也可能溢出。对策分析数据范围预估中间结果大小。默认使用long long64位进行计算特别是涉及乘法、求幂时。在求LCM时务必使用a / gcd(a, b) * b。对于更大的数需要使用高精度计算用数组或字符串模拟。问题2循环边界与精度陷阱for (int i 1; i sqrt(n); i)。sqrt(n)返回double对于完全平方数如n25sqrt(25)在计算机中可能是4.999999...导致i4.999为真i5时循环不执行漏掉了约数5。解决方案使用i * i n注意溢出或更安全的i n / i。问题3重复添加约数在试除法中对于完全平方数n当i等于sqrt(n)时i和n/i是同一个数。如果不加判断if (i ! n / i)就会在约数列表中添加两次。检查用完全平方数如3649测试你的getDivisors函数看输出是否正确。问题4算法复杂度估计错误新手容易写出O(n)的求约数循环当n很大时程序超时。调试对于输入规模大的题目先在本地用最大边界值测试运行时间。养成习惯看到“求约数”第一反应就应该是O(√n)的试除法或筛法。问题5特殊输入处理n0或n1明确题目定义。通常我们讨论的是正整数约数。0的约数定义有争议1只有1个约数。负数如果题目可能包含负数需要明确是否考虑负约数。通常可以先取绝对值处理再根据题意调整。调试技巧实录小数据测试用几个小例子如n1, 2, 6, 12, 16, 25手动计算预期结果与程序输出对比。打印中间变量在循环中打印i,n%i等值观察程序实际执行流程。边界测试用int最大值INT_MAX约21亿附近的数测试检查溢出和效率。使用标准库对照对于GCD可以用C17的std::gcd来验证自己实现的正确性。5. 性能优化与进阶话题5.1 从O(√n)到更优Pollard-Rho算法当n非常大比如10^18时即使是O(√n)的试除法也无法在短时间内完成质因数分解。这时就需要更高级的算法如Pollard-Rho算法。它是一种概率性算法用于快速找到大整数的一个非平凡因子即不是1和它本身的因子。其核心思想是利用生日悖论和Floyd判圈算法通过一个随机生成的函数序列来寻找n的因子。期望时间复杂度约为O(n^{1/4})对于大数分解是革命性的。不过其实现较为复杂涉及模运算、随机数生成和最大公约数计算。通常只在专门的数论库或应对极端情况时使用。5.2 预处理与查询的权衡在算法竞赛或高频查询的业务场景中我们需要在“预处理耗时”和“单次查询耗时”之间做权衡。场景A少量查询n很大- 对每个查询单独用试除法或高级算法。场景B大量查询Q次n在中等范围如N≤10^6- 使用筛法O(N log log N)预处理出所有数的约数列表/个数/和然后每次查询O(1)响应。总复杂度O(N log log N Q)远优于O(Q√N)。场景C需要频繁获取某个数的所有约数- 可以预处理出每个数的最小质因子然后在查询时利用质因数分解公式和递归方法在O(log n)时间内动态生成所有约数比存储所有约数列表更省空间。5.3 多线程与并发计算在极其追求性能的场合如科学计算求一个大数的所有约数可以被并行化。因为检查i和n/i是否能整除n是相互独立的。可以将区间[1, √n]分成若干段交给多个线程同时进行试除最后合并结果。但需要注意线程同步和负载均衡。对于质因数分解Pollard-Rho算法本身也有并行化的变种。6. 一个综合案例解决“因子求和”问题让我们用一个经典问题来串联所学知识“求一个正整数n的所有真约数之和”。问题分析真约数之和等于约数之和减去n本身。我们可以用两种方法方法A直接试除遍历1到√n累加约数对i和n/i最后减去n。时间复杂度O(√n)空间复杂度O(1)。方法B公式法先质因数分解再利用约数和公式计算σ(n)最后减去n。分解质因数最坏也是O(√n)但对于有很多小质因子的数分解很快。C实现对比#include iostream #include cmath using namespace std; // 方法A试除法直接求和 long long sumProperDivisors_direct(int n) { if (n 1) return 0; long long sum 0; for (int i 1; i n / i; i) { if (n % i 0) { sum i; if (i ! n / i i ! 1) { // 注意1和n本身这里我们求真约数不包含n sum n / i; } } } // 上面的循环当i1时加了1当in时不会进入因为in/i // 所以sum现在包含1。真约数之和是除了n以外的所有约数和所以就是当前的sum因为没加n // 但注意当i是n的平方根时我们只加了一次i。需要仔细处理。 // 更清晰的写法 sum 0; for (int i 1; i n / i; i) { if (n % i 0) { sum i; if (i ! n / i) { sum n / i; } } } return sum - n; // 总和减去自己得到真约数和 } // 方法B公式法需要质因数分解和快速幂 long long quickPow(long long a, int b) { long long res 1; while (b) { if (b 1) res * a; a * a; b 1; } return res; } long long sumProperDivisors_formula(int n) { int temp n; long long sum 1; for (int i 2; i temp / i; i) { if (temp % i 0) { int cnt 0; while (temp % i 0) { cnt; temp / i; } sum * (quickPow(i, cnt 1) - 1) / (i - 1); } } if (temp 1) { sum * (quickPow(temp, 2) - 1) / (temp - 1); } return sum - n; } int main() { int n 28; // 完全数28124714 cout Direct method: sumProperDivisors_direct(n) endl; cout Formula method: sumProperDivisors_formula(n) endl; // 验证 cout Is 28 a perfect number? (sumProperDivisors_direct(n) n ? Yes : No) endl; return 0; }选择建议对于单个查询两种方法复杂度相当。试除法代码更简单不易出错。如果需要多次查询不同n的约数和且n值较大公式法配合预处理的最小质因子筛可能会更有优势因为质因数分解可以很快。如果n非常大超过10^12试除法可能太慢而公式法中的质因数分解也会变慢可能需要Pollard-Rho算法。我个人在实际编码中对于int范围内的数更倾向于使用试除法因为它直白、不容易在边界条件上出错而且现代CPU执行O(√n)次循环对于n10^9也就约3万次迭代是瞬间完成的。代码的清晰度和可维护性往往是第一位的除非性能测试表明这里成了瓶颈。