计算自然数n非素正约数之和的子函数实现与问题排查

• 约数枚举与累加逻辑完全错位
  原代码在循环内的累加判断没有和整除判断绑定：只要之前发现n存在约数（prim被置为0），就会把所有遍历到的d值直接加到累加和中，会大量把不能整除n的非约数错误计入结果；同时仅遍历了小于等于sqrt(n)的小值侧数值，完全没有处理每对整除关系中大于sqrt(n)的配对约数（即n/d形式的约数），导致绝大多数真实约数被遗漏。例如计算n=16时，原代码会把非约数的d=3错误计入，最终返回9，和正确结果29差距极大。
• 约数的素数属性筛选完全缺失
  题目要求累加n的所有非素正约数，需要对每一个找到的约数单独判断：如果约数本身是素数，必须排除后再累加。原代码中的prim变量仅用于标记n自身是否为素数，完全没有针对单个约数的素数属性做校验，会错误把素数约数计入累加和。
• 边界场景处理失效
  当n为小于4的素数（如2、3）时，循环会因为d*d>n直接退出，累加和s始终保持初始值0，完全没有把非素的基础约数1计入结果，返回值不符合要求。
• 配对约数去重逻辑缺失
  即使补全约数枚举规则，当d是n的平方根整数时，d和n/d是同一个值，若不做去重判断会导致该约数被重复累加，造成结果偏大。

实现思路 #

1. 适配[1, 1e6]的输入范围，采用sqrt(n)的约数枚举法，将循环复杂度控制在O(sqrt(n))，在1e6的输入规模下仅需最多1000次循环，运行效率足够。
2. 内嵌轻量的素数判断逻辑，对每个枚举到的约数做素数属性校验，仅保留非素约数做累加。
3. 单独处理1和n本身两个特殊约数，避免遗漏；对配对约数做去重判断，避免重复累加。

完整代码 #

// 辅助判断：输入x是否为素数，是则返回1，否则返回0
int is_prime(int x)
{
    if (x < 2) return 0;
    if (x == 2) return 1;
    if (x % 2 == 0) return 0;
    for (int i = 3; i * i <= x; i += 2)
    {
        if (x % i == 0)
            return 0;
    }
    return 1;
}

int suma(int n)
{
    // 边界处理：n=1时唯一的正约数是1，且1非素，直接返回1
    if (n == 1)
        return 1;
    
    // 1是所有大于1的正整数的约数，且非素，初始计入累加和
    int sum = 1;
    
    // 枚举约数，遍历范围到sqrt(n)即可覆盖所有整除对
    for (int d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
        {
            // 处理当前小值约数d，非素则累加
            if (!is_prime(d))
                sum += d;
            
            // 处理配对的大值约数n/d，和d不相等且非素则累加，避免重复
            int paired = n / d;
            if (paired != d && !is_prime(paired))
                sum += paired;
        }
    }
    
    // 处理n本身这个约数，非素则累加
    if (!is_prime(n))
        sum += n;
    
    return sum;
}

正确性验证 #

• 示例输入n=12：枚举得到的非素约数为1、4、6、12，累加和1+4+6+12=23，和题目要求的返回值一致。
• 边界输入n=1：返回1，符合规则。
• 边界输入n=2（素数）：唯一非素约数为1，返回1，符合规则。
• 输入n=16：非素约数为1、4、8、16，累加和为29，逻辑计算正确。

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