{- |
Description: Euler's totient function with Euler's product formula
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P37" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P37 (totient') where

import           Problems.P36

-- | Calculate Euler's totient function \(\phi(m)\) using Euler's product formula.
totient' :: Integral a => a -> a
totient' :: forall a. Integral a => a -> a
totient' a
m = [a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ ((a, a) -> a) -> [(a, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (\(a
p, a
k) -> a
pa -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a
^(a
ka -> a -> a
forall a. Num a => a -> a -> a
-a
1) a -> a -> a
forall a. Num a => a -> a -> a
* (a
pa -> a -> a
forall a. Num a => a -> a -> a
-a
1)) [(a, a)]
factors
  where factors :: [(a, a)]
factors = a -> [(a, a)]
forall a. Integral a => a -> [(a, a)]
primeFactorsMultiplicity a
m