求给定数质因数之和的Haskell函数出现无限循环问题求助

问题定位 #

• 无限循环触发场景：当输入n=1时，sumPrimeDivs的辅助函数helper里d从2开始持续递增，但永远达不到d == num=1的终止条件，直接陷入无限递归。
• 额外逻辑缺陷：
  • 输入为质数时（如5），辅助函数走到d == num分支直接返回初始的result=0，漏掉了将质数自身计入总和的逻辑。
  • 找到质因数后未对num做除法处理，无法正确计算重复质因数的和（比如输入4，若需计算重复质因数和，当前逻辑只能得到2，而非4）。
  • 第一个分支的表达式helper num (d + 1) result + d虽然不会引发循环，但递归调用优先于加法的写法容易混淆执行顺序，可读性差。

修复后的代码 #

isPrime :: Int -> Bool
isPrime n
  | n <= 1    = False
  | n == 2    = True
  | even n    = False
  | otherwise = helper 3
  where
    helper d
      | d * d > n = True
      | mod n d == 0 = False
      | otherwise = helper (d + 2)

sumPrimeDivs :: Int -> Int
sumPrimeDivs n
  | n <= 1    = 0
  | isPrime n = n
  | otherwise = helper n 2 0
  where
    helper num d result
      | d * d > num = if isPrime num then result + num else result
      | isPrime d && mod num d == 0 =
          let newNum = div num d
          in if newNum == num
             then result + d
             else helper newNum d (result + d)
      | otherwise = helper num (d + 1) result

调试建议 #

• 先测边界值：优先测试n=1、n=2、负数这类边界输入，这类情况最容易暴露循环或逻辑漏洞。
• 打印递归状态：用Debug.Trace模块的trace函数打印每次递归的num、d、result，直观观察递归路径：

  import Debug.Trace
  helper num d result = trace (show (num, d, result)) $
    -- 原有分支逻辑
  

• 明确终止条件：把递归的终止条件放在分支最前面，避免因条件顺序错误导致终止条件被跳过。
• 优化质数判断：原isPrime遍历到n效率太低，改成遍历到sqrt(n)，同时提前排除偶数，减少递归次数。

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