如何在Racket中实现更高效率的sum-of-divisors约数求和算法？

现有实现问题说明 #

• 最初的暴力遍历版本时间复杂度为O(n)，n较大时耗时高是必然结果，你的优化方向完全正确，不需要更换思路，只需要修正优化版本的逻辑错误即可。
• 你写的优化版存在两个核心错误：
  1. 整除判断逻辑错误：你判断的是i能否整除floor(sqrt n)，实际应该判断i能否整除目标数n
  2. 终止条件返回值逻辑混乱，不符合约数求和的规则

最优实现代码 #

首先保留你已经写好的工具函数：

(define divides?
  (lambda (a b)
    (= (remainder b a) 0)))

优化后的约数总和实现：

(define (sum-of-divisors n)
  (define sqrt-n (integer-sqrt n))
  (let loop ([i 1] [sum 0])
    (cond
      [(> i sqrt-n) sum]
      [(divides? i n)
       (loop (add1 i)
             (if (= i (/ n i))
                 (+ sum i)
                 (+ sum i (/ n i))))]
      [else (loop (add1 i) sum)])))

实现说明 #

• 时间复杂度为O(√n)，相比原暴力版本性能提升幅度和n的大小正相关：比如n为10^6时，原版本要遍历100万次，优化版本仅需遍历1000次，性能远超你要求的降至原耗时5%的目标。
• 特殊处理完全平方数场景：当n是完全平方数时，√n只会被加一次，避免重复计算。
• 测试验证：(sum-of-divisors 6)返回结果为12，和你给出的预期结果一致。

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