Haskell实现返回(素因子,幂次)元组的素因数分解函数

实现思路 #

先枚举所有因子再筛素数的写法存在冗余计算，性能较差。Haskell中完全可以把常规命令式的循环逻辑改写为天然的递归结构，在试除分解的过程中直接统计每个素因子的幂次，不需要单独维护列表计数，也不需要额外的素数判断函数——从小到大试除时，合数因子的素因子会先被除尽，因此能整除当前数的因子必然是素数。

核心逻辑分两部分：

• 幂次统计：对当前试除的因子d，连续除以d直到不能整除，记录除的次数就是d的幂次，同时返回除完后的剩余数
• 递归分解：从最小素数2开始逐个数试除，每统计完一个因子的幂次，就对剩余数从下一个因子开始继续分解，直到剩余数为1为止

完整可运行实现 #

primeFactorization :: Integer -> [(Integer, Integer)]
primeFactorization 1 = [] -- 边界值：1没有素因子
primeFactorization n = decompose n 2
  where
    -- 递归分解函数：参数1为待分解的剩余数，参数2为当前试除的起始因子
    decompose 1 _ = []
    decompose remain d
      -- 剩余数小于d的平方，说明剩余数本身是素数，直接加入结果
      | d*d > remain = [(remain, 1)]
      -- 当前因子能整除剩余数，统计幂次后继续分解剩余部分
      | remain `mod` d == 0 =
          let (power, nextRemain) = countPower remain d 0
          in (d, power) : decompose nextRemain (d + 1)
      -- 当前因子不能整除，试下一个数
      | otherwise = decompose remain (d + 1)

    -- 统计因子d在num中的最高幂次，返回(幂次, 除尽d^k后的剩余数)
    countPower num d acc
      | num `mod` d /= 0 = (acc, num)
      | otherwise = countPower (num `div` d) d (acc + 1)

效果验证 #

在GHCi中加载上述代码后执行：

> primeFactorization 120
[(2,3),(3,1),(5,1)]

输出完全符合预期，对应分解式120 = 2^3 * 3^1 *5^1。

基于原有代码的修改方案（不推荐，性能较差） #

如果要保留之前写的因子筛选、素数判断逻辑，只需要补充幂次统计逻辑即可，但这种写法在处理大素数时会枚举2到n-1的所有数，效率很低，仅作参考：

primeFactorization :: Integer -> [(Integer, Integer)]
primeFactorization n = 
    let
        factors :: Integer -> [Integer]
        factors n = [x | x <- [2..n-1], n `mod` x == 0]

        isPrime :: Integer -> Bool
        isPrime n
            | n `elem` [0, 1] = False
            | n == 2 = True
            | n > 2 = null [ x | x <- [2..(ceiling . sqrt . fromIntegral) n], n `mod` x == 0]
            | otherwise = False
        
        primeList = filter isPrime $ factors n
        -- 统计单个素因子的幂次
        countPow _ 1 acc = acc
        countPow p num acc
          | num `mod` p == 0 = countPow p (num `div` p) (acc + 1)
          | otherwise = acc
    in
        -- 过滤幂次为0的项，补上可能遗漏的自身为素数的边界情况
        filter (\(_,k) -> k>0) (map (\p -> (p, countPow p n 0)) primeList)
        ++ if n > 1 && isPrime n then [(n,1)] else []

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