如何在C语言中不使用数学库实现O(√n)复杂度的is_abundant函数？

原代码问题分析 #

你提供的原代码存在两个核心问题：

1. 时间复杂度高：遍历范围是1到num-1，时间复杂度为O(n)，对于大数效率极低；
2. 真因数和计算错误：初始sum=1后，循环又重复累加了因数1，最终减num得到的结果不符合真因数和的定义。

优化思路 #

丰数的判断依赖真因数和（不包含自身的所有正因数之和），而因数具有成对性：若i是num的因数，则num/i也必然是其因数。利用这一特性，只需遍历到√num即可找到所有因数对，无需遍历到num-1，从而将时间复杂度降至O(√n)。同时：

• 用i*i <= num替代数学库的sqrt函数，避免依赖外部库；
• 处理完全平方数时，需避免重复累加同一个因数；
• 修正真因数和的计算逻辑，避免重复累加因数1。

优化后的完整代码 #

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int is_abundant(int num);
int main()
{
    int num;
    scanf("%d", &num);
    printf("%d\n", is_abundant(num));
    return 0;
}

int is_abundant(int num)
{
    // 1及以下的数没有足够的真因数，无法成为丰数
    if (num <= 1) {
        return 0;
    }
    int sum = 1; // 1是所有大于1的正整数的真因数，仅累加一次
    // 遍历到i*i <= num，等价于遍历到√num，无需数学库
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            sum += i;
            int pair_factor = num / i;
            // 完全平方数的两个因数相同，避免重复累加
            if (pair_factor != i) {
                sum += pair_factor;
            }
        }
    }
    // 丰数定义：真因数和大于自身则返回1，否则返回0
    return sum > num ? 1 : 0;
}

关键优化点说明 #

• 循环范围缩减：通过i*i <= num控制循环上限，仅遍历到√num，大幅减少迭代次数；
• 因数对处理：每找到一个因数i，同时将对应的配对因数num/i加入总和，仅当两者不同时才累加（避免完全平方数重复计算）；
• 边界情况处理：直接排除num<=1的情况，这类数无法满足丰数的定义；
• 逻辑修正：初始sum=1仅累加一次因数1，后续不再重复计算，确保真因数和的准确性。

内容的提问来源于stack exchange，提问作者Wael Jaber