约数算法优化：从O(n)到O(√n)的高效实现

1. 约数基础与高效算法对比

约数（因数）是数学和编程中的基础概念，指能整除给定整数的所有正整数。对于编程新手来说，理解约数的数学本质和高效计算方法至关重要。我们先从最直观的传统方法开始分析。

1.1 传统循环方法的局限性

传统方法采用从1到n的完整遍历，虽然逻辑简单直接，但存在明显的效率问题。以n=10000为例，传统方法需要进行10000次循环判断，而实际上只需要100次循环即可完成（√10000=100）。这种效率差异随着n的增大呈指数级扩大。

cpp复制// 传统方法时间复杂度分析
for(int i=1; i<=n; i++) {  // O(n)时间复杂度
    if(n%i == 0) {
        // 处理约数
    }
}

1.2 基于对称性的优化原理

高效算法的核心在于利用约数的对称特性：若i是n的约数，则n/i必然也是约数。这个数学性质让我们只需要遍历到√n即可获取所有约数。具体来说：

• 对于n=12，当发现2是约数时，可以同时确定6也是约数(12/2=6)
• 对于n=16，当发现4是约数时，需要注意避免重复添加(16/4=4)

这种优化将时间复杂度从O(n)降低到O(√n)，对于大数运算效率提升显著。

2. 高效算法的实现细节

2.1 基础实现与边界处理

高效算法的标准实现需要考虑几个关键细节：

cpp复制vector<int> getDivisors(int n) {
    vector<int> divisors;
    for(int i=1; i*i<=n; i++) {  // 使用i*i避免浮点运算
        if(n%i == 0) {
            divisors.push_back(i);
            if(i != n/i) {       // 避免平方数重复
                divisors.push_back(n/i);
            }
        }
    }
    sort(divisors.begin(), divisors.end());  // 排序输出
    return divisors;
}

这里特别需要注意的是循环条件的写法。相