« Project euler : Problem 2 〜 フィボナッチ数 | トップページ | Project Euler : Problem 4 ~ 回文数 »

2009年12月 3日 (木)

Project euler : Problem 3 ~ 素因数分解

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

 いわゆる素因数分解の問題ですね。
 というわけで Haskell でも素因数分解をする関数を作ってみました。

 一番単純な試し割り法ですが、そこそこ速いので Project Euler を解くにはこの位で十分かなと思っています。
 後々のことを考えて、結果は素因数と次数をペアにしたものをリストにまとめる形にしました。

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 main = print $ factorize 600851475143

 Ruby や Scheme で作ったものと比べると、コードの長さが約半分位になっています。

« Project euler : Problem 2 〜 フィボナッチ数 | トップページ | Project Euler : Problem 4 ~ 回文数 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project euler : Problem 3 ~ 素因数分解:

« Project euler : Problem 2 〜 フィボナッチ数 | トップページ | Project Euler : Problem 4 ~ 回文数 »

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            
フォト

最近のトラックバック

無料ブログはココログ