{- |
Description: Gaussian primes
Copyright: Copyright (C) 2022 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P44" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P44 (isGaussianPrime) where

import           Data.Complex
import           Data.List            ((\\))
import           Problems.P43         (gaussianDividesBy)
import           Solutions.Arithmetic (gaussianMultiply, gaussianUnits)

-- | Determine whether a Gaussian integer is a Gaussian prime.
isGaussianPrime :: Complex Integer -> Bool
isGaussianPrime :: Complex Integer -> Bool
isGaussianPrime (Integer
0 :+ Integer
0) = Bool
False
isGaussianPrime (Integer
1 :+ Integer
0) = Bool
False
isGaussianPrime ((-1) :+ Integer
0) = Bool
False
isGaussianPrime (Integer
0 :+ Integer
1) = Bool
False
isGaussianPrime (Integer
0 :+ (-1)) = Bool
False
isGaussianPrime Complex Integer
x = [Complex Integer] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([Complex Integer] -> Bool) -> [Complex Integer] -> Bool
forall a b. (a -> b) -> a -> b
$ [Complex Integer]
divisors [Complex Integer] -> [Complex Integer] -> [Complex Integer]
forall a. Eq a => [a] -> [a] -> [a]
\\ [Complex Integer]
exclusions
  where divisors :: [Complex Integer]
divisors = (Complex Integer -> Bool) -> [Complex Integer] -> [Complex Integer]
forall a. (a -> Bool) -> [a] -> [a]
filter (Complex Integer -> Complex Integer -> Bool
gaussianDividesBy Complex Integer
x) ([Complex Integer] -> [Complex Integer])
-> [Complex Integer] -> [Complex Integer]
forall a b. (a -> b) -> a -> b
$ Complex Integer -> [Complex Integer]
candidates Complex Integer
x
        exclusions :: [Complex Integer]
exclusions = [Complex Integer]
associates [Complex Integer] -> [Complex Integer] -> [Complex Integer]
forall a. [a] -> [a] -> [a]
++ [Complex Integer]
gaussianUnits
        associates :: [Complex Integer]
associates = (Complex Integer -> Complex Integer)
-> [Complex Integer] -> [Complex Integer]
forall a b. (a -> b) -> [a] -> [b]
map (Complex Integer -> Complex Integer -> Complex Integer
gaussianMultiply Complex Integer
x) [Complex Integer]
gaussianUnits

candidates :: Complex Integer -> [Complex Integer]
candidates :: Complex Integer -> [Complex Integer]
candidates (Integer
a :+ Integer
b) = [ Integer
x Integer -> Integer -> Complex Integer
forall a. a -> a -> Complex a
:+ Integer
y  | Integer
x <- [Integer
0..Integer
bound], Integer
y <- [Integer
0..Integer
bound] ]
  where norm :: Integer
norm = Integer -> Integer
forall {a}. Num a => a -> a
square Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer -> Integer
forall {a}. Num a => a -> a
square Integer
b
        bound :: Integer
bound = (Integer -> Bool) -> (Integer -> Integer) -> Integer -> Integer
forall a. (a -> Bool) -> (a -> a) -> a -> a
until (\Integer
x -> (Integer -> Integer
forall {a}. Num a => a -> a
square (Integer -> Integer) -> (Integer -> Integer) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
forall {a}. Num a => a -> a
square) Integer
x Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
norm) (Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
1) Integer
1
        square :: a -> a
square a
x = a
xa -> a -> a
forall a. Num a => a -> a -> a
*a
x