P33 - 判断互质
Determine whether two positive integers are coprime
官方模块：
Problems.P33核心函数：coprime
题目描述
如果两个整数的最大公约数为 1，就称它们互质。互质不要求两个数本身都是素数，例如 35 和 64 互质。
函数签名
1coprime :: Integral a => a -> a -> Bool
实现
方法一：基于 GCD（最直接）
1coprime :: Integral a => a -> a -> Bool
2coprime a b = myGCD a b == 1
P32 已经完成全部计算，这道题的重点是把数学定义直接组合成程序。
方法二：不用 GCD，遍历检查公因数
1coprime :: Integral a => a -> a -> Bool
2coprime a b = null [d | d <- [2..min (abs a) (abs b)], a `mod` d == 0 && b `mod` d == 0]
直接从定义出发：不存在大于 1 的公因数。效率低但逻辑显式。
方法三：只枚举到平方根
1coprime :: Integral a => a -> a -> Bool
2coprime a b = all noCommonFactor [1..integerSqrt smaller]
3 where
4 smaller = min (abs a) (abs b)
5 noCommonFactor divisor
6 | smaller `mod` divisor /= 0 = True
7 | otherwise =
8 not (nonTrivial divisor && abs b `mod` divisor == 0)
9 && not (nonTrivial paired && abs b `mod` paired == 0)
10 where
11 paired = smaller `div` divisor
12 nonTrivial factor = factor > 1
13
14integerSqrt :: Integral a => a -> a
15integerSqrt n = last (takeWhile (\x -> x * x <= n) [0..])
只枚举到平方根时，必须同时检查成对因子 smaller div divisor。例如 7 和 14 的公共因子 7 大于 ，但它会作为因子 1 的配对项被检查到。
方法对比
| 方法 | 特点 | 效率 |
|---|---|---|
| GCD 法 | 一句话，最简洁 | O(log min(a,b)) |
| 枚举公因数 | 从定义出发，教学直观 | O(min(a,b)) |
| 枚举到 √n | 不依赖 GCD，比方法二快 | O(√min(a,b)) |
测试
1>>> coprime 35 64
2True
3>>> coprime 21 14
4False
5>>> coprime 1 100
6True
7>>> coprime 7 14
8False