C++高效计算约数：从试除法到筛法，原理与实战详解

1. 约数：从数学概念到程序实现的核心解析

约数，或者叫因数，这个概念我们小学就学过。一个整数a能被另一个整数b整除，我们就说b是a的约数。听起来简单吧？但就是这个简单的概念，在编程，尤其是算法竞赛和底层系统优化里，扮演着极其关键的角色。无论是判断一个数是否为质数、求最大公约数（GCD）来简化分数，还是解决一些看似复杂的数论问题，比如“完全数”、“亲和数”，甚至是RSA加密算法的基础，都离不开对约数的高效计算和深入理解。

在C++的世界里，处理约数不仅仅是数学问题，更是对程序效率的极致考验。一个新手可能会写一个从1遍历到n的循环来找出所有约数，这在n很小的时候没问题。但当n是一个十几位的大整数时，这种暴力方法的耗时将是灾难性的。这就引出了我们讨论的核心：如何利用数学性质，在C++中优雅且高效地处理约数相关的问题。本文将从一个C++开发者的实战角度，彻底拆解约数的求法、应用以及那些容易踩坑的细节，目标是让你看完之后，不仅能写出代码，更能理解背后的“为什么”，在面试或实际项目中遇到相关问题能游刃有余。

2. 约数基础与高效求解算法

2.1 约数的定义与基本性质

在深入代码之前，我们必须夯实数学基础。对于整数a和b（b ≠ 0），如果存在整数k，使得 a = k × b，那么b就是a的约数。例如，12的约数有1, 2, 3, 4, 6, 12。

这里有几个关键性质直接影响我们的算法设计：

1. 成对出现：如果d是n的约数，那么n/d也一定是n的约数。比如6是12的约数，那么12/6=2也是约数。这个性质是优化遍历范围的核心。
2. 平凡约数：1和n本身总是n的约数。
3. 平方根特性：对于任意一个约数对(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; vector<int> getDivisors(int n) { vector<int> 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; vector<int> 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是约数个数。对于需要有序约数的场景，这是必要的。如果后续使用不要求顺序，可以省略排序以提升性能。
• 边界情况：n=0时，任何非零数都是0的约数（因为0除以任何数等于0），但通常题目中会规定正整数。n=1时，约数只有1。我们的代码能正确处理这些情况吗？对于n=1，sqrt(1)=1，循环会执行一次，i=1，n%i=0，插入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，共有(ai+1)种选择。所有选择独立相乘，就得到了所有可能的约数数量。
  • 举例：180 = 2^2 * 3^2 * 5^1。约数个数 = (2+1)(2+1)(1+1) = 332 = 18。
• 约数和公式：σ(n) = (p1^(a1+1)-1)/(p1-1) * (p2^(a2+1)-1)/(p2-1) * ... * (pk^(ak+1)-1)/(pk-1)
  • 原理：这是等比数列求和公式的应用。对于质因数pi，其贡献的因子和是1 + pi + pi^2 + ... + pi^ai = (pi^(ai+1)-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; } pair<int, long long> getDivisorCountAndSum(int n) { int temp = n; map<int, 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^(a+1)-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; }

实操心得：

1. 质因数分解的效率：上述分解算法复杂度约为O(√n)。对于单个大数，这已经不错。但如果需要对一个范围内的所有数进行预处理，就需要更高效的筛法（如欧拉筛）来快速获取质因数。
2. 快速幂的必要性：在计算约数和时，p^(a+1)可能非常大。直接使用pow函数（浮点数版本）会有精度损失，使用循环乘会超时。因此快速幂算法是必备技能，它能在O(log b)时间内计算a^b。
3. 数据类型选择：约数和可能增长得非常快，很容易超出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> // C++17起，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; // C++17 cout << "LCM(" << x << ", " << y << ") = " << lcm(x, y) << endl; return 0; }

注意事项：

• 负数处理：GCD通常定义为正数。上述自定义实现对于负数输入，结果可能为负。标准库的std::gcd返回非负结果。在实际应用中，可以先取绝对值abs()。
• 零的处理：gcd(a, 0) = |a|。我们的迭代版本能正确处理（当b=0时循环结束，返回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)，对于N=10^6就已经力不从心了。

这时就需要筛法。其核心思想是“用约数去找倍数”，而不是“用数去找约数”。

埃拉托斯特尼筛法求质数是筛法的经典代表。类似的，我们可以修改筛法来预处理每个数的约数信息。

应用1：用筛法求1~N每个数的约数个数思路：初始化一个数组div_cnt[N+1]，全部为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; vector<int> getDivisorCountUpTo(int N) { vector<int> 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[N+1]，初始化为1。对于每个数i，将其加到所有它的倍数j的div_sum[j]上。

vector<long long> getDivisorSumUpTo(int N) { vector<long 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 应用场景举例

1. 分数化简：在实现分数类（Fraction）时，分子分母同除以它们的最大公约数（GCD）即可得到最简分数。

   struct Fraction { long long num, den; void simplify() { long long g = std::gcd(num, den); // C++17 num /= g; den /= g; if (den < 0) { num = -num; den = -den; } // 保证分母为正 } };

2. 周期性问题：许多循环、模拟问题中，周期长度往往是相关数字的最小公倍数（LCM）。例如，多个齿轮同时转动，回到初始位置的时间是它们周期的最小公倍数。

3. 完全数与亲和数判断：

   • 完全数：一个数等于它的所有真约数（除了自身以外的约数）之和。如6=1+2+3。
   • 亲和数：两个数，其中一个数的所有真约数之和等于另一个数，反之亦然。如(220, 284)。 判断这类数都需要高效计算约数和。

4. 加密算法基础：RSA公钥加密算法的安全性基于大整数的质因数分解难题，而密钥生成过程中大量用到求模逆元，这又依赖于扩展欧几里得算法（GCD算法的扩展）。

4.2 常见问题、陷阱与调试技巧

问题1：整数溢出这是数论问题中最常见的坑。即便输入在int范围内，中间计算结果（如乘法、幂运算）也可能溢出。

• 对策：
  • 分析数据范围，预估中间结果大小。
  • 默认使用long long（64位）进行计算，特别是涉及乘法、求幂时。
  • 在求LCM时，务必使用a / gcd(a, b) * b。
  • 对于更大的数，需要使用高精度计算（用数组或字符串模拟）。

问题2：循环边界与精度

• 陷阱：for (int i = 1; i <= sqrt(n); i++)。sqrt(n)返回double，对于完全平方数如n=25，sqrt(25)在计算机中可能是4.999999...，导致i<=4.999为真，i=5时循环不执行，漏掉了约数5。
• 解决方案：使用i * i <= n（注意溢出）或更安全的i <= n / i。

问题3：重复添加约数在试除法中，对于完全平方数n，当i等于sqrt(n)时，i和n/i是同一个数。如果不加判断if (i != n / i)，就会在约数列表中添加两次。

• 检查：用完全平方数（如36，49）测试你的getDivisors函数，看输出是否正确。

问题4：算法复杂度估计错误新手容易写出O(n)的求约数循环，当n很大时程序超时。

• 调试：对于输入规模大的题目，先在本地用最大边界值测试运行时间。养成习惯：看到“求约数”，第一反应就应该是O(√n)的试除法或筛法。

问题5：特殊输入处理

• n=0或n=1：明确题目定义。通常我们讨论的是正整数约数。0的约数定义有争议，1只有1个约数。
• 负数：如果题目可能包含负数，需要明确是否考虑负约数。通常可以先取绝对值处理，再根据题意调整。

调试技巧实录：

1. 小数据测试：用几个小例子（如n=1, 2, 6, 12, 16, 25）手动计算预期结果，与程序输出对比。
2. 打印中间变量：在循环中打印i,n%i等值，观察程序实际执行流程。
3. 边界测试：用int最大值（INT_MAX，约21亿）附近的数测试，检查溢出和效率。
4. 使用标准库对照：对于GCD，可以用C++17的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本身。我们可以用两种方法：

1. 方法A（直接试除）：遍历1到√n，累加约数对（i和n/i），最后减去n。时间复杂度O(√n)，空间复杂度O(1)。
2. 方法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; } } } // 上面的循环，当i=1时，加了1，当i=n时不会进入（因为i<=n/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; // 完全数28=1+2+4+7+14 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)次循环（对于n=10^9，也就约3万次迭代）是瞬间完成的。代码的清晰度和可维护性往往是第一位的，除非性能测试表明这里成了瓶颈。