P34 - 欧拉函数
Calculate Euler’s totient function
官方模块：
Problems.P34核心函数：totient
题目描述
欧拉函数 表示 中与 互质的整数个数。
函数签名
1totient :: Integral a => a -> a
实现
方法一：筛选计数（定义直译）
1totient :: Integral a => a -> a
2totient m
3 | m < 1 = error "totient: positive input required"
4 | otherwise = fromIntegral . length $ filter (coprime m) [1..m]
定义的直接翻译：从 1 到 m 筛出与 m 互质的数，再计数。P37 会用欧拉乘积公式将它优化。
方法二：递归遍历
1totient :: Integral a => a -> a
2totient 1 = 1
3totient n = go 1 0
4 where
5 go m acc
6 | m > n = acc
7 | coprime m n = go (m + 1) (acc + 1)
8 | otherwise = go (m + 1) acc
不用 filter 和 length，手动递归计数。减少了列表构造的内存开销。
方法三：内联 gcd 检查（不依赖 P33）
1totient :: Integral a => a -> a
2totient 1 = 1
3totient n = fromIntegral $ length [x | x <- [1..n], myGCD x n == 1]
不依赖 P33 的 coprime，直接调用 P32 的 myGCD。本质上和方法一相同，但依赖关系更浅。
方法对比
| 方法 | 代码量 | 依赖 | 特点 |
|---|---|---|---|
| filter + coprime | 1 行 | P33 | 最抽象，语义清晰 |
| 递归遍历 | 6 行 | P33 | 无中间列表 |
| 列表推导 + myGCD | 1 行 | P32 | 最少外部依赖 |
测试
1>>> totient 1
21
3>>> totient 10
44
5>>> totient 315
6144
因为 1、3、7、9 与 10 互质，所以 。