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