{- |
Description: List of prime factors
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

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

import           Solutions.Arithmetic

-- | Determine the prime factors of a given positive integer.
-- Construct a list containing the prime factors in ascending order.
primeFactors :: Integral a => a -> [a]
primeFactors :: forall a. Integral a => a -> [a]
primeFactors a
n = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a] -> [a] -> [a]
forall a. Integral a => a -> [a] -> [a] -> [a]
factor a
n [a]
forall a. Integral a => [a]
primes []

factor :: Integral a => a -> [a] -> [a] -> [a]
factor :: forall a. Integral a => a -> [a] -> [a] -> [a]
factor a
1 [a]
_ [a]
fs = [a]
fs
factor a
n ps' :: [a]
ps'@(a
p:[a]
ps) [a]
fs
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
pa -> a -> a
forall a. Num a => a -> a -> a
*a
p         = a
n a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
fs
  | a
n a -> a -> Bool
forall a. Integral a => a -> a -> Bool
`dividesBy` a
p = a -> [a] -> [a] -> [a]
forall a. Integral a => a -> [a] -> [a] -> [a]
factor (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
p) [a]
ps' (a
pa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
fs)
  | Bool
otherwise       = a -> [a] -> [a] -> [a]
forall a. Integral a => a -> [a] -> [a] -> [a]
factor a
n [a]
ps [a]
fs
factor a
_ [a]
_ [a]
_ = [a]
forall a. HasCallStack => a
undefined