top page > computer > haskell > web_lecture > for_programmer > factorization.html
更新日:
文責: 重城良国

素因数分解

factorization.hs

素因数分解とは

素因数分解とは数を素数の積で表現することだ。

420 = 2 * 2 * 3 * 5 * 7

大きな数の素因数分解を効率的に行うアルゴリズムはない。

考えかた

素因数分解は

  1. 整数を2以上の最小の約数と残りの数に分ける
  2. 残りの数についてそれをくりかえす

のようにする。

最小の約数

整数nの最小の約数を求める。2以上の整数のリストの各要素でnを割り0になるものだけを集めその先頭をとる。2以上のnで、filterの結果のリストの要素数は1以上だ。よってnが2以上であることが保証されていれば関数headの適用は安全だ。

head $ filter ((== 0) . (n `mod`)) [2 ..]

最小の約数と残りの数

最小の約数でもとの数をわれば残りの数となる。2未満のときはそれ以上わけられないと考えてNothingとする。

popFactor :: Integer -> Maybe (Integer, Integer)
popFactor n | n < 2 = Nothing
popFactor n = Just (f, n `div` f)
where f = head $ filter ((== 0) . (n `mod`)) [2 ..]

% ghci factorization.hs
*Main> popFactor 95
Just (5,19)
*Main> popFactor 11183
Just (53,211)

素因数分解

popFactor nの結果によって以下のような値を返せば良い。

factorization :: Integer -> [Integer]
factorization n = case popFactor n of
Nothing -> []
Just (f, n') -> f : factorization n'

*Main> :reload
*Main> factorization 163761
[3,13,13,17,19]
*Main> factorization 30566863
[30566863]
*Main> factorization 45598842
[2,3,3,3,61,109,127]

桁数の多い素数を引数とするとプロンプトが返ってこなくなるので気をつけよう。

関数iterateの枠組みとの比較

関数iterateでは次々にわたしていく値と結果としてリストに入る値は同じだ。たとえばコラッツ数列の例では5の次の値は16であるが、この16は結果のリストに入りかつ残りの値を求めるのに使われる。しかし素因数分解の例では

だ。素因数分解する関数は関数iterateの枠組みをそのまま使うことはできない。

関数unfoldrの使用

結果のリストに入る値と次を求める値とが異なるときは関数unfoldrが使える。この関数では終了条件も指定できる。

値 -> Maybe (結果, 次の値)

のような関数と初期値をとり生成されるリストを返す。

関数popFactorがこの形だ。よってfactorizationは以下のように書き換えられる。

factorization = unfoldr popFactor

unfoldrを使うにはData.Listモジュールが必要だ。以下をファイルの先頭に追加する。

import Data.List

*Main> :reload
*Main> factorization 45598842
[2,3,3,3,61,109,127]

まとめ

素因数分解の例を学んだ。関数iterateの枠組みでは表現できない「結果と途中の値とが違う」例だ。このような関数は関数unfoldrで表現できる。

「関数iterateの定義」へもどる 「関数unfoldrの定義」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics