From 9db0008777cc4cd9f07e14a3458e3d903e3cc4f6 Mon Sep 17 00:00:00 2001 From: Determinant Date: Mon, 29 May 2017 13:29:11 -0400 Subject: finish vol 4 --- 31-41/37.hs | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) create mode 100644 31-41/37.hs (limited to '31-41/37.hs') diff --git a/31-41/37.hs b/31-41/37.hs new file mode 100644 index 0000000..ead0514 --- /dev/null +++ b/31-41/37.hs @@ -0,0 +1,19 @@ +import Data.List (group, foldl') + +primeFactors :: Int -> [Int] + +primeFactors x = factor x primes + where primes = filterPrime [2..] + filterPrime (p:xs) = p:filterPrime [x | x <- xs, x `mod` p /= 0] + factor x l@(p:xs) + | p > x = [] + | x `mod` p == 0 = p:factor (x `div` p) l + | otherwise = factor x xs + +primeFactorsMult :: Int -> [(Int, Int)] + +primeFactorsMult x = [(head l, length l) | l <- group $ primeFactors x] + +phi :: Int -> Int + +phi x = foldl' (\acc (p, m) -> acc * (p - 1) ^ m) 1 (primeFactorsMult x) -- cgit v1.2.3