EulerQ3.hs

-- Q3: The prime factors of 13195 are 5, 7, 13 and 29.
-- What is the largest prime factor of the number 600851475143 ?

-- Q3 take1 (not used)
isDiv :: Int -> Int -> Bool
isDiv x y = mod x y == 0

factors :: Int -> [Int]
factors x = filter (isDiv x) [1,2..x]

prime :: Int -> Bool
prime x = (factors x) == [1,x]

primeFactors :: Int -> [Int]
primeFactors x = filter prime $ factors x
-- Waaaaaaay too slow

-- Q3 take2
reduce :: Int -> [Int] -> Int
reduce n (a:xs)
  | a < n = if mod n a == 0 then reduce (div n a) xs else reduce n xs
  | otherwise = n
ans3 = reduce 600851475143 (2:[3,5..])