finish vol 4

1 files changed, 19 insertions, 0 deletions

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)