素因数分解プログラム

素因数分解するプログラムを作ってみた。プログラムは次のようになる。factors 関数は引数に素因数分解する数をとり、値に素因数分解のリストを返す。

Prelude> seive (x:xs) = x : sieve (filter (\y -> y `mod` x /= 0) xs)
Prelude> primes = seive [2..]
Prelude> factor n (x:xs) | n `mod` x == 0 = x | otherwise = factor n xs
Prelude> :{
Prelude| factors 1 = []
Prelude| factors n =
Prelude|   let p = factor n primes
Prelude|   in p : factors (n `div` p)
Prelude| :}

実行例は次のようになる。

Prelude> factors 2021
[43,47]

エラトステネスのふるい

先ず素数の無限リストを作るが、その前にエラトステネスのふるいを行う関数 sieve を定義する。

sieve (x:xs) = x : sieve (filter (\y -> y `mod` x /= 0) xs)

sieve は引数に数値のリストをとる。値は素数のリストだ。したがって与える数値のリストは先頭に素数を置いた自然数の数列でないといけない。引数の先頭の要素 x が 2 だとするとこれは素数だ。それで x : と素数のリストの先頭に置く x に続く素数のリストは (x:xs) の数列の先頭の x を除いた xs に sieve を関数適用して作る。したがって、

x : sieve xs

で良さそうだが、xs の先頭は素数ではないかもしれない。そこで、xs のうち x で割れないものだけを取り出す。それが次の式だ。

filter (\y -> y `mod` x /= 0) xs

これはエラトステネスのふるいの場合もやっている操作だ。したがって、最終的な定義は冒頭のものと同じだが次のようになる。

sieve (x:xs) = x : sieve (filter (\y -> y `mod` x /= 0) xs)

このふるい関数 sieve を使って素数の無限リストをつくるが、単に無限リスト [2..] に sieve を関数適用するだけだ。

primes = seive [2..]

素因数を求める

素数の無限リストができたので後はそれを使って素因数分解することになる。そこで、最初に自然数 n の素因数の最も小さいものを求める関数 factor を定義する。

factor n (x:xs) | n `mod` x == 0 = x | otherwise = factor n xs

factor は２つの引数をとる。一つは因数を求める数 n だ。もう一つは素因数を小さい順に収めた素数のリストだ。 まずは素数のリストの先頭の要素 x について n を割り切ることができるかを調べる。素数リストの先頭の要素でたまたま割り切れた場合はその先頭要素 x を返す。すなわち、

n `mod` x == 0 = x

である。

n が x で割り切れないときは x を取り除いた xs という素数のリストについて最検索をする。

otherwise = factor n xs

このように素数リスト (x:xs) を先頭から１個ずつ調べることで n の素因数を求めることができる。

素因数分解する

自然数 n のすべての素因数を求める関数 factors は次のようになる。

Prelude| factors 1 = []
Prelude| factors n =
Prelude|   let p = factor n primes
Prelude|   in p : factors (n `div` p)

n が 1 のときは素因数はないので factors 1 = [] である。

次は一般的な、自然数 n の場合についても定義してみる。まずは n の最も小さな素因数を求めて p とする。

let p = factor n primes

この p を使って factors の値のリストを作る。まず p はリストの先頭に置く p : だ、その後には n の値を p で割った値の factors のリストが続く。

in p : factors (n `div` p)

この p : factors (n `div` p) が求める素因数分解のリストだ。

複雑なアルゴリズムも、単純なアルゴリズムに分解することによって、コードに落とし込むことができるのが面白い。コードを読むことはアルゴリズムを読むことだ。その際に、記号と一緒に自然言語でアルゴリズムを記述することではるかに理解しやすくなるのがわかる。単なる、コメントではなく、アルゴリズムをしっかりと自然言語で表現することが大切だ。