---------------------
-- Timing function --
---------------------
import Text.Printf
import System.CPUTime

timeIO :: IO t -> IO t
timeIO y = do
    start <- getCPUTime
    x     <- y
    end   <- getCPUTime
    let diff = (fromIntegral (end - start)) / (10^12)
    printf "Computation time: %0.3f sec\n" (diff :: Double)
    return x

time :: (Show t) => t -> IO ()
time x = do
    timeIO $ do
        r <- return x
        printf "%s\n" $ show r
        return r
    return ()

----------------------
-- Function library --
----------------------

ceilSqrt :: Integral a => a -> a
ceilSqrt = ceiling . sqrt . fromIntegral

fibs :: Integral a => [a]
fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

fib :: Integral a => Int -> a
fib n = fibs !! n

------------
-- Primes --
------------

is_prime :: Integral a => a -> Bool
is_prime 2 = True -- 2 will divide by itself in the generic test; 3+ are fine
is_prime n = foldl (\acc x -> if n `mod` x == 0 then False else acc) True $ takeWhile (<= ceilSqrt n) (2:[3,5..])

prime_sieve :: Integral a => [a]
prime_sieve = filter is_prime [2..]

prime_divisors :: Integral a => a -> [a]
prime_divisors x =
    let y = map fst $ filter ((==0) . snd) $              -- get all numbers which divide x exactly
            takeWhile ((<= ceilSqrt x) . fst) $           -- for values up to sqrt x
            zip prime_sieve $ (map (mod x) $ prime_sieve) -- that are prime
    in y ++ if is_prime x then [x] else []                -- and also add x to the list if x is prime

factors :: Integral a => a -> [a]
factors 1 = []
factors x = let y = head $ prime_divisors x -- get the smallest prime divisor
            in y:factors (x `div` y)        -- use that divisor and append factor x `div` divisor

-- Function Library End

euler01 = let
    threes = [3,6..999]
    fives  = [5,10..999]
    dupes  = [ x | x <- threes, y <- fives, x == y ]
    in sum [ sum threes, sum fives, 0 - (sum dupes) ]

euler02 = sum $ filter even $ takeWhile (<4000000) fibs

euler03 = last $ factors 600851475143

-- NOTE: VERY VERY SLOW
euler05 = let
    div_test d n = foldl (\acc x -> if n `mod` x /= 0 then False else acc) True [d,d-1..((d + 1) `div` 2)]
    in fst $ head $ filter snd $ zip [1..] $ map (div_test 20) [1..]