{- |
Description: Primality checking
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P31" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P31 (isPrime, isPrime', isPrime'') where

import           Solutions.Arithmetic

-- | Determine whether a given integer number is prime.
--
-- Checks whether the integer is even or if there is a divisor
-- among odd integers not greater than its square root.
isPrime :: Integral a => a -> Bool
isPrime :: forall a. Integral a => a -> Bool
isPrime a
n
  | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
2         = Bool
True
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
2          = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a
n `dividesBy`) ([a] -> Bool) -> [a] -> Bool
forall a b. (a -> b) -> a -> b
$ a
2 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
odds
  | Bool
otherwise      = Bool
False
  where odds :: [a]
odds = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\a
k -> a
ka -> a -> a
forall a. Num a => a -> a -> a
*a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
n) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate (a
2+) a
3

-- | Determine whether a given integer number is prime.
--
-- Uses an Erastothenes sieve to construct a list of primes up
-- to at least the square root of the integer, and searches for
-- a divisor among them.
isPrime' :: Integral a => a -> Bool
isPrime' :: forall a. Integral a => a -> Bool
isPrime' a
n
  | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
2    = Bool
True
  | a -> Bool
forall a. Integral a => a -> Bool
even a
n    = Bool
False
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
2     = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a
n `dividesBy`) [a]
ps
  | Bool
otherwise = Bool
False
  where ps :: [a]
ps = [a] -> [a]
forall a. Integral a => [a] -> [a]
sieve ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\a
k -> a
ka -> a -> a
forall a. Num a => a -> a -> a
*a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
n) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate (a
2+) a
3)

sieve :: Integral a => [a] -> [a]
sieve :: forall a. Integral a => [a] -> [a]
sieve []     = []
sieve (a
n:[a]
ns) = a
n a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
forall a. Integral a => [a] -> [a]
sieve ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> Bool
forall a. Integral a => a -> a -> Bool
dividesBy a
n) [a]
ns)

-- | Determine whether a given integer number is prime.
--
-- From a list of all prime numbers, search for a divisor.
isPrime'' :: Integral a => a -> Bool
isPrime'' :: forall a. Integral a => a -> Bool
isPrime'' a
n
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
1     = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a
n `dividesBy`) ([a] -> Bool) -> [a] -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\a
k -> a
ka -> a -> a
forall a. Num a => a -> a -> a
*a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
n) [a]
forall a. Integral a => [a]
primes
  | Bool
otherwise = Bool
False