P44 - 朴素判定高斯素数

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

P44 - 朴素判定高斯素数

Determine whether a Gaussian integer is prime

官方模块：Problems.P44　核心函数：isGaussianPrime

← P43 高斯整数整除 | P45 二平方定理判定 →

题目描述

高斯整数的单位元为 ±1,±i\pm1,\pm i。若一个非零非单位高斯整数除单位元和自身的相伴元外没有其他因子，它就是高斯素数。

函数签名

1isGaussianPrime :: Complex Integer -> Bool

实现

方法一：枚举候选因子

 1import Data.Complex (Complex((:+)))
 2
 3isGaussianPrime :: Complex Integer -> Bool
 4isGaussianPrime z
 5  | nz <= 1   = False
 6  | otherwise = not (any (z `gaussianDividesBy`) candidates)
 7  where
 8    nz = normSquared z
 9    limit = integerSqrt (nz - 1)
10    candidates =
11      [x :+ y | x <- [-limit..limit], y <- [-limit..limit]
12              , let nd = x*x + y*y, nd > 1, nd < nz]
13
14normSquared :: Complex Integer -> Integer
15normSquared (a :+ b) = a*a + b*b
16
17integerSqrt :: Integer -> Integer
18integerSqrt n = last (takeWhile (\x -> x*x <= n) [0..])

用范数 N(a+bi)=a2+b2N(a+bi)=a^2+b^2 衡量大小。真正的非单位因子 d 必须满足 1<N(d)<N(z)1<N(d)<N(z)，枚举这个有限区域并复用 P43 的整除判断。

方法二：只枚举上半平面

 1isGaussianPrime :: Complex Integer -> Bool
 2isGaussianPrime z
 3  | nz <= 1   = False
 4  | otherwise = not (any (z `gaussianDividesBy`) candidates)
 5  where
 6    nz = normSquared z
 7    limit = integerSqrt (nz - 1)
 8    candidates =
 9      [(x :+ y) | x <- [0..limit], y <- [-limit..limit]
10                , let nd = x*x + y*y, nd > 1, nd < nz
11                , nd <= nz - 1]

利用对称性只枚举 x≥0x \ge 0 的一半区间，减少约一半的检查量。

方法三：预筛法优化

 1isGaussianPrime :: Complex Integer -> Bool
 2isGaussianPrime z
 3  | nz <= 1   = False
 4  | otherwise = null [d | d <- candidateNorms
 5                        , let ds = integerSqrt d
 6                        , x <- [-ds..ds], y <- [-ds..ds]
 7                        , x*x + y*y == d
 8                        , z `gaussianDividesBy` (x :+ y)]
 9  where
10    nz = normSquared z
11    candidateNorms = [d | d <- [2..nz-1], nz `mod` d == 0]

先枚举范数的因数，再检查是否有对应的高斯整数因子。减少了对 gaussianDividesBy 的无效调用。

方法对比

方法枚举量特点
全枚举(2L+1)2(2L+1)^2最直接，易懂
上半平面(L+1)(2L+1)(L+1)(2L+1)利用对称性优化
范数因数预筛取决于因数个数对合数最优

测试

1>>> isGaussianPrime (0 :+ 5)
2False
3>>> isGaussianPrime (17 :+ 0)
4False
5>>> isGaussianPrime (5 :+ 2)
6True

参考