P37 - 欧拉乘积公式求 φ(n)

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

P37 - 欧拉乘积公式求 φ(n)

Euler’s totient function with Euler’s product formula

官方模块：Problems.P37　核心函数：totient'

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

核心公式

若 m=∏ipikim=\prod_i p_i^{k_i}，则

φ(m)=∏ipiki−1(pi−1). \varphi(m)=\prod_i p_i^{k_i-1}(p_i-1).

函数签名

1totient' :: Integral a => a -> a

实现

方法一：基于 P36 的质因数分解

1totient' :: Integral a => a -> a
2totient' m
3  | m < 1     = error "totient': positive input required"
4  | otherwise = product
5      [p ^ (k - 1) * (p - 1) | (p, k) <- primeFactorsMultiplicity m]

P36 已经给出所有 (pi,ki)(p_i,k_i)，这里只需逐项映射并相乘。空乘积等于 1，所以 totient' 1 会自然得到 1。

方法二：不用 P36，只用 P35 的质因数列表

1import Data.List (group)
2
3totient' :: Integral a => a -> a
4totient' m
5  | m < 1     = error "totient': positive input required"
6  | otherwise = foldl apply m (group (primeFactors m))
7  where
8    apply n xs = n `div` p * (p - 1)
9      where p = head xs

从 φ(m)=m∏p∣m(1−1/p)\varphi(m) = m\prod_{p|m}(1-1/p) 出发，每遇到一个不同质因数，做 n / p * (p-1)。不依赖 primeFactorsMultiplicity，只依赖 primeFactors。

方法三：与 P34 对比的定义法

1totient' :: Integral a => a -> a
2totient' m = totient m   -- 复用 P34 的定义实现

如果要对比性能，可以直接调用 P34。对小数字结果相同，对大数字 P34 慢得多。

方法对比

方法复杂度依赖特点
乘积公式 + P36O(√m)P36标准做法，推荐
逐个质因数约化O(√m)P35不需要重数信息
P34 定义法O(m log m)P34仅用于验证一致性

测试

1>>> totient' 10
24
3>>> totient' 315
4144
5>>> all (\n -> totient n == totient' n) [1..100]
6True

参考