[[ProjectEular]]

 -- Common.hs
 
 module Common (
     fibs
 ,   factorize
 ,   divisors
 ,   proper_divisors
 ,   is_prime
 ) where
 
 
 ------------------------------
 -- Export functions
 ------------------------------
 
 -- Get Fibonacci sequence
 fibs :: (Integral a) => [a]
 fibs = 1 : 2 : zipWith (+) fibs (tail fibs)
 
 -- Prime factorization
 factorize :: (Integral a) => a -> [a]
 factorize n = factorize_iter n (2:[3,5..])
 
 -- Get divisors
 divisors :: (Integral a) => a -> [a]
 divisors num = divisors_iter num [1..]
 
 -- Get proper divisors (== divisors of N except for N)
 proper_divisors :: (Integral a) => a -> [a]
 proper_divisors = init . divisors
 
 -- Is a prime number or not
 is_prime :: (Integral a) => a -> Bool
 is_prime n = is_prime_iter n (2:[3,5..])
 
 
 ------------------------------
 -- Non-export functions
 ------------------------------
 
 -- For prime factorization
 factorize_iter :: (Integral a) => a -> [a] -> [a]
 factorize_iter n (x:xs)
     | n < x^2      = [n]
     | mod n x == 0 = x : (factorize_iter (div n x) (x:xs))
     | otherwise    = factorize_iter n xs
 -- For getting divisors
 divisors_iter :: (Integral a) => a -> [a] -> [a]
 divisors_iter n (x:xs)
     | n < x^2                = []
     | mod_ == 0 && div_ == x = x : (divisors_iter n xs)
     | mod_ == 0 && div_ /= x = x : (divisors_iter n xs) ++ [div_]
     | otherwise              = divisors_iter n xs
     where (div_,mod_) = divMod n x
 
 -- For is_prime
 is_prime_iter :: (Integral a) => a -> [a] -> Bool
 is_prime_iter n (x:xs)
     | n <= 1       = False
     | n < x^2      = True
     | mod n x == 0 = False
     | otherwise    = is_prime_iter n xs
トップ   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS