P35 - 质因数分解

2026-09-07 00:00    #Haskell   #99题   #数论  

P35 - 质因数分解

Determine the prime factors of a positive integer

官方模块：Problems.P35　核心函数：primeFactors

← P34 欧拉函数 | P36 带重数的质因数分解 →

题目描述

把正整数分解为按升序排列的质因数列表，重复因子要重复出现。例如 315=3×3×5×7315=3\times3\times5\times7。

函数签名

1primeFactors :: Integral a => a -> [a]

实现

方法一：试除递归（2, 3, 5, 7, …）

 1primeFactors :: Integral a => a -> [a]
 2primeFactors n
 3  | n < 1     = error "primeFactors: positive input required"
 4  | otherwise = factor n 2
 5  where
 6    factor 1 _ = []
 7    factor x d
 8      | d * d > x      = [x]
 9      | x `mod` d == 0 = d : factor (x `div` d) d
10      | d == 2         = factor x 3
11      | otherwise      = factor x (d + 2)

找到因子后仍用同一个 d 继续除，从而保留重数。若 d2>xd^2>x，剩余的 xx 必然是质数。

方法二：基于 P39 的素数列表

 1primeFactors :: Integral a => a -> [a]
 2primeFactors n
 3  | n < 1     = error "primeFactors: positive input required"
 4  | otherwise = factor n primes
 5  where
 6    factor 1 _ = []
 7    factor x (p:ps)
 8      | p * p > x   = [x]
 9      | x `mod` p == 0 = p : factor (x `div` p) (p:ps)
10      | otherwise   = factor x ps

只试除已知的素数，而不是全部奇数。对于大质因数的情况，比方法一节省约一半的试除次数。

方法三：迭代式（不使用递归）

 1import Data.List (unfoldr)
 2
 3primeFactors :: Integral a => a -> [a]
 4primeFactors n
 5  | n < 1     = error "primeFactors: positive input required"
 6  | otherwise = unfoldr factor n
 7  where
 8    factor 1 = Nothing
 9    factor x = case filter (\d -> x `mod` d == 0) candidates of
10      []  -> Just (x, 1)
11      p:_ -> Just (p, x `div` p)
12      where
13        candidates = takeWhile (\d -> d * d <= x) [2..]

用 unfoldr 生成器风格表达分解过程。每步找到最小的质因数，输出它，继续分解剩余部分。代码更函数式但效率不如方法一。

方法对比

方法试除对象特点
试除奇数2, 3, 5, 7…自包含，无外部依赖
素数列表P39 的 primes试除次数最少
unfoldr 迭代动态枚举函数式风格，代码最简洁

测试

1>>> primeFactors 315
2[3,3,5,7]
3>>> primeFactors 13
4[13]
5>>> primeFactors 1
6[]

参考