C++中如何高效计算斐波那契数的约数个数？

算力阿峰

2026-5-22

优化C++中约数个数计算的高效实现

嘿，我来帮你搞定这个约数个数计算的效率问题！你的当前代码循环到val/2确实会浪费很多计算资源——毕竟大多数数的约数都远小于它的一半，而且完全没利用约数的对称性。咱们来一步步优化它：

核心优化思路：利用约数的对称性

对于任意正整数val，如果i是它的约数，那么val/i也必然是它的约数。基于这个特性，我们只需要循环到sqrt(val)就足够了，这样循环次数直接从O(n)降到O(√n)，效率提升非常明显。

优化后的代码实现

int nrdiv(int val) {
    // 处理特殊值：0和1的约数只有1个
    if (val <= 1) {
        return 1;
    }
    
    int count = 0;
    int sqrt_val = static_cast<int>(sqrt(val));
    
    for (int i = 1; i <= sqrt_val; ++i) {
        if (val % i == 0) {
            // 如果i和val/i是同一个数（完全平方数的情况），只计数一次
            if (i == val / i) {
                count++;
            } else {
                // 否则两个都是约数，计数加2
                count += 2;
            }
        }
    }
    
    return count;
}

验证你的测试用例

输入21：sqrt(21)≈4.58，循环i从1到4：
- i=1：21%1==0，1≠21 → count +=2 → count=2
- i=2：21%2≠0 → 跳过
- i=3：21%3==0，3≠7 → count +=2 → count=4
- i=4：21%4≠0 → 跳过
  最终返回4，符合预期。
输入124：sqrt(124)≈11.13，循环i从1到11：
- i=1：124%1==0，1≠124 → count +=2 → count=2
- i=2：124%2==0，2≠62 → count +=2 → count=4
- i=4：124%4==0，4≠31 → count +=2 → count=6
  其余i均不整除124，最终返回6，完全正确。