P45 - 二平方定理判定高斯素数
Determine Gaussian primality using the two-square theorem
官方模块：
Problems.P45核心函数：isGaussianPrime'
← P44 朴素判定高斯素数 | P46 二元逻辑真值表 →
题目描述
用数论定理取代 P44 的因子枚举，高效判定高斯素数。
判定定理
高斯整数 为素数，当且仅当满足以下一种情况：
- ，且 是模 4 余 3 的普通素数；
- ，且 是模 4 余 3 的普通素数；
- 都非零，且 是普通素数。
函数签名
1isGaussianPrime' :: Complex Integer -> Bool
实现
方法一：整系数数论判定（推荐）
1import Data.Complex (Complex((:+)))
2
3isGaussianPrime' :: Complex Integer -> Bool
4isGaussianPrime' (a :+ 0) =
5 abs a `mod` 4 == 3 && isPrime (abs a)
6isGaussianPrime' (0 :+ b) =
7 abs b `mod` 4 == 3 && isPrime (abs b)
8isGaussianPrime' (a :+ b) = isPrime (a*a + b*b)
与 P44 的二维因子枚举相比，这里只做至多一次 的普通素数判断。
方法二：封装 P44 的枚举法（验证用）
1isGaussianPrime' :: Complex Integer -> Bool
2isGaussianPrime' = isGaussianPrime -- 复用 P44 的定义枚举
如果需要对比 P44 和 P45 的结果是否一致，可以直接调用 P44。
方法三：合并实数轴判定的简化版
1isGaussianPrime' :: Complex Integer -> Bool
2isGaussianPrime' (a :+ b)
3 | a == 0 || b == 0 = let n = abs (a + b) in n `mod` 4 == 3 && isPrime n
4 | otherwise = isPrime (a*a + b*b)
将两个实数轴的情况合并为 n = abs (a+b)（因为其中一个为 0）。
方法对比
| 方法 | 复杂度 | 特点 |
|---|---|---|
| 数论判定 | O(√n) | 标准做法，推荐 |
| P44 枚举 | O(n²) | 用于验证一致性 |
| 合并实数轴 | O(√n) | 代码更紧凑 |
测试
1>>> isGaussianPrime' (0 :+ 5)
2False
3>>> isGaussianPrime' (17 :+ 0)
4False
5>>> isGaussianPrime' (5 :+ 2)
6True
7>>> isGaussianPrime' (3 :+ 0)
8True
要点总结
P44 从定义出发，P45 从结构定理出发。二者结果相同，但后者展示了数学结论如何直接改变算法复杂度。