素因数分解

Haskell で素因数分解をどう記述するのかネットで調べてみた。いろいろな解答があったが、一番わかりやすかったのがこれ。

factors :: Integer -> [Integer]
factors n = [x | x <- [1..n], n `mod` x == 0]

factorization :: Integer -> [Integer]
factorization 1 = []
factorization x = v : factorization (x `div` v)
  where
    v = (factors x) !! 1

imHo さんの 素因数分解を求めるgolf という記事に掲載されていた。

上のプログラムで factors n は、n の約数のリスト。 (factors n) !! 1 は約数のうちの1以外の最小のもの。
Main> factors 12
[1,2,3,4,6,12]
Main> (factors 12) !! 1
2

factorization は、n を最小の約数で次々割っていって、n が 1 になったら終了する。簡単なアルゴリズムだが、600851475143 の素因数分解もすぐに結果が出た。
Main> factorization 600851475143
[71,839,1471,6857]

すごい!!


今日の Haskell
Main> minimum [2,0,1,0,11,22]
0
Main> maximum [2,0,1,0,11,22]
22

こういう小道具をたくさん道具箱に入れておくのが、Haskell 職人への道だろう。
[PR]
by tnomura9 | 2010-11-23 02:50 | Haskell | Comments(0)
<< 二次式の因数分解 3の倍数と3のつく数 >>