gistfile1.hs

import Data.List (nub, group)
-- problem 31

isPrime :: Int -> Bool
isPrime n = length (filter (\x -> (mod n x) == 0) [2..n-1]) == 0 && n > 1

-- problem 32
pgcd :: Int ->  Int -> Int
pgcd a 0 = a
pgcd a b = pgcd b (mod a b)


-- problem 33
coprime :: Int -> Int -> Bool
coprime a b = pgcd a b == 1

-- problem 34
totientPhi :: Int -> Int
totientPhi n = length $ filter (\x -> x == True) $ map (\x -> coprime n x) [1..n]

primes n = [x | x <- [2..n-1], isPrime x]

-- problem 35
primeFactor :: Int -> [Int]
primeFactor n =  reverse $ helper n (reverse $ primes n) [] 
                           where helper 1 _ acc = acc
                                 helper n [] acc = acc
                                 helper n (x:xs) acc = if mod n x == 0 then helper (div n x) xs (acc ++ [x]) else helper n xs acc


generatePrimeFactor :: Int -> [Int] -> [Int] -> [Int]
generatePrimeFactor 1 _ acc = acc
generatePrimeFactor n [] acc = acc
generatePrimeFactor n p@(x:xs) acc = if mod n x == 0 then generatePrimeFactor (div n x) p (acc ++ [x]) else generatePrimeFactor n xs acc

primeFactorAsc :: Int -> [Int]
primeFactorAsc n =  nub $ generatePrimeFactor n (primes n) [] 


primeFactorAsc' :: Int -> [(Int, Int)]
primeFactorAsc' n =  map (\x -> (length x, head x)) $ group $ generatePrimeFactor n (primes n) []