« Project Euler : Problem 4 ~ 回文数 | トップページ | Project Euler : Problem 6 »

2009年12月19日 (土)

Project Euler : Problem 5 ~ 最小公倍数

 問題はこちらをご覧ください。

 要するに最小公倍数を求める問題です。
 Haskell には標準ライブラリに「lcm」があるので、

problem005 :: Integral a => a -> a problem005 n = foldr1 lcm [1 .. n] main = print $ problem005 20
で、終わってしまいます。

 

 これではあまりにも簡単過ぎるので、もうちょっと遊んでみましょう。

 では、自分で最小公倍数を求める関数を作ってみます。
 整数 a, b の最大公約数を gcd(a, b)、最小公倍数を lcm(a, b) とすると、lcm(a, b) = a * b / gcd(a, b) となります。そこで、最大公約数を求める "gcd'" を「ユークリッドの互除法」を使って実装し、それを使って "lcm'" を実装してみます。

gcd' m 0 = m gcd' m n = gcd' n (mod m n) lcm' m n = div (m * n) (gcd' m n) main = print $ foldr1 lcm' [1 .. 20]

 

 次に、ちょっと違う方向から考えてみましょう。
 2 〜 20 までの数を素因数分解した場合、すべての素因数をひとつずつ(同じ素因数が複数個ある場合はもっとも次数の大きいもの)を集めていくと答えが出るはずです。

import Data.List (group) -- 素因数分解 factorize :: Integral a => a -> [(a, Int)] factorize 1 = [(1, 0)] factorize n = format $ factorize' n divs where divs = 2 : 3 : [x + y | x <- [6, 12 ..], y <- [-1, 1]] factorize' n xs'@(x : xs) | n < x * x = [n] | rem n x == 0 = x : factorize' (div n x) xs' | otherwise = factorize' n xs format = map (\xs -> (head xs, length xs)) . group maxFactors :: Integral a => [(a, Int)] -> [(a, Int)] -> [(a, Int)] maxFactors xs [] = xs maxFactors xs ((f, i) : ys) | null bs = maxFactors ((f, i) : xs) ys | i > (snd $ head bs) = maxFactors (as ++ ((f, i) : tail bs)) ys | otherwise = maxFactors xs ys where (as, bs) = break (\ x -> fst x == f) xs problem005 :: Integral a => a -> a problem005 n = product $ map (\x -> (fst x) ^ (snd x)) xs where xs = foldr1 maxFactors $ map factorize [2 .. n] main = print $ problem005 20
 やたら長くなりましたが、ちゃんと答えは出ます。
 でも、やっぱり一番最初のコードが一番いいですね。

« Project Euler : Problem 4 ~ 回文数 | トップページ | Project Euler : Problem 6 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47060176

この記事へのトラックバック一覧です: Project Euler : Problem 5 ~ 最小公倍数:

« Project Euler : Problem 4 ~ 回文数 | トップページ | Project Euler : Problem 6 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ