P36 - 质因数分解（含重数）
Determine the prime factors and their multiplicities
官方模块：
Problems.P36核心函数：primeFactorsMultiplicity
题目描述
把 P35 的重复质因数压缩成 (质因数, 重数)。例如 [3,3,5,7] 变为 [(3,2),(5,1),(7,1)]。
函数签名
1primeFactorsMultiplicity :: Integral a => a -> [(a, a)]
实现
方法一：group + map
1import Data.List (group)
2
3primeFactorsMultiplicity :: Integral a => a -> [(a, a)]
4primeFactorsMultiplicity = map encode . group . primeFactors
5 where
6 encode xs = (head xs, fromIntegral (length xs))
P35 保证因数有序，因此相同因数必然连续，group 可以直接打包。head 在这里是安全的，因为 group 不会生成空子列表。
方法二：打包时不依赖 group
1primeFactorsMultiplicity :: Integral a => a -> [(a, a)]
2primeFactorsMultiplicity n = pack (primeFactors n)
3 where
4 pack [] = []
5 pack (x:xs) = (x, 1 + length ys) : pack zs
6 where (ys, zs) = span (== x) xs
用 span 手动切分连续相同元素，效果等同于 group 但不依赖 Data.List。
方法三：直接边分解边计数（不依赖 P35）
1primeFactorsMultiplicity :: Integral a => a -> [(a, a)]
2primeFactorsMultiplicity n
3 | n < 1 = error "primeFactorsMultiplicity: positive input required"
4 | otherwise = factor n 2
5 where
6 factor 1 _ = []
7 factor x d
8 | d * d > x = [(x, 1)]
9 | x `mod` d == 0 = (d, count) : factor remaining nextDivisor
10 | d == 2 = factor x 3
11 | otherwise = factor x (d + 2)
12 where
13 (count, remaining) = divideOut x d 0
14 nextDivisor = if d == 2 then 3 else d + 2
15
16 divideOut value divisor count
17 | value `mod` divisor == 0 =
18 divideOut (value `div` divisor) divisor (count + 1)
19 | otherwise = (count, value)
边分解边统计重数。更紧凑但可读性不如先分解再 group。
方法对比
| 方法 | 特点 |
|---|---|
| group + map | 最清晰，推荐 |
| span 手动分组 | 不依赖 Data.List |
| 边分解边计数 | 一通到底，不依赖 P35 |
测试
1>>> primeFactorsMultiplicity 315
2[(3,2),(5,1),(7,1)]
3>>> primeFactorsMultiplicity 81
4[(3,4)]
5>>> primeFactorsMultiplicity 1024
6[(2,10)]
7>>> primeFactorsMultiplicity 1
8[]