C++约数试除法：原理、实现与优化技巧

1. 约数试除法基础解析

约数试除法是数论中最基础的算法之一，也是C++编程竞赛和面试中的高频考点。它的核心思想是通过遍历可能的候选数来寻找目标数的所有约数，这种朴素的暴力解法虽然简单，但在许多场景下却非常实用。

1.1 数学原理与算法思想

试除法的数学基础在于约数的成对出现特性。对于任意整数n，如果d是n的一个约数，那么n/d也必定是n的约数。这意味着我们只需要检查从1到√n的整数，就能找到所有的约数对。

算法步骤可以分解为：

1. 初始化一个空容器用于存储约数
2. 遍历i从1到√n：
   • 如果n能被i整除：
     • 将i加入约数列表
     • 如果i≠n/i，将n/i也加入约数列表
3. 对约数列表进行排序（可选）
4. 返回约数列表

这个算法的时间复杂度是O(√n)，空间复杂度取决于约数的数量，最坏情况下是O(√n)（当n为完全平方数时）。

1.2 C++实现基础版本

让我们先看一个最基础的实现版本：

cpp复制#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

std::vector<int> getDivisors(int n) {
    std::vector<int> divisors;
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }
    std::sort(divisors.begin(), divisors.end());
    return divisors;
}

int main() {
    int num = 36;
    std::vector<int> divisors = getDivisors(num);
    for (int d : divisors) {
        std::cout << d << " ";
    }
    return 0;
}

这个实现有几个值得注意的点：

1. 使用sqrt(n)作为循环上限，而不是n，这大大减少了循环次数
2. 每次找到约数时，同时存储i和n/i这对约数
3. 最后对结果进行排序，使约数以升序输出

注意：sqrt()函数返回的是浮点数，但在与整数比较时会自动转换。有些编译器可能会给出警告，更严谨的写法是使用i*i <= n作为循环条件。

2. 算法优化与进阶实现

基础版本虽然简单