Problem 37 - Euler's totient function optimized
phi : Int -> Int
phi n =
if n < 1 then
0
else
List.product
<| List.map (\( p, m ) -> (p - 1) * p ^ (m - 1))
<| primeFactorsM n
primeFactorsM : Int -> List ( Int, Int )
primeFactorsM n =
toTuples <| primeFactors n
primeFactors : Int -> List Int
primeFactors n =
if n < 2 then
[]
else
let
prime =
Maybe.withDefault 0
<| List.head
<| dropWhile (\x -> n % x /= 0) (List.range 2 n)
in
prime :: (primeFactors <| n // prime)
dropWhile : (a -> Bool) -> List a -> List a
dropWhile predicate list =
case list of
[] ->
[]
x :: xs ->
if (predicate x) then
dropWhile predicate xs
else
list
takeWhile : (a -> Bool) -> List a -> List a
takeWhile predicate xs =
case xs of
[] ->
[]
hd :: tl ->
if (predicate hd) then
hd :: takeWhile predicate tl
else
[]
toTuples : List a -> List ( a, Int )
toTuples fs =
case fs of
[] ->
[]
x :: xs ->
( x, List.length (takeWhile (\y -> y == x) fs) )
:: toTuples (dropWhile (\y -> y == x) fs)
Back to problem