１．素因数分解
自然数を素数の積として表すのが素因数分解である。例えば、35という数は、素数5と7の積としてあらわすことができる。それでは自然数が与えられた時、それを素因数分解するプログラムを考えよう。与えらえた自然数を\(n\)とする。素数は次のように求めることができる。2からはじめて、\(\sqrt{n}\)に近い自然数までの中で、元の数を割ることができないものが、素数である。
従って、自然数\(n\)に対して素数\(p\)が一つもとまったとき、次の素数は、自然数\(n'=\frac{n}{p}\)の素数を求めればよい。この操作を素数が求まらなくなるまで続ければよいので、プログラムは次のようになる。プログラムで、where以下のyを得ているところが、このプルグラムの主要な部分であり、ここで、素数を一つ求めている。
prime :: Int -> [Int] prime n = prime' n [] prime' n x | y == [] = n : x | otherwise = prime' (div n (head y)) ((head y) : x) where y = take 1 $ [x | x <- [2.. truncate $ sqrt $ fromIntegral n], mod n x == 0]
これを実行すると次のようになる。
*Main> prime 1052 [263,2,2] *Main> prime 1024 [2,2,2,2,2,2,2,2,2,2]
２．因数分解
多項式の因数分解は高校の数学で学ぶ。例えば、多項式\(x^2 -6 \times x+8\)を因数に分解すると、\(x -4\)と\(x -2\)を得る。
多項式の因数分解を行うプログラムを考えてみることにする。ただし、ここでは係数はすべて整数である物を考える。従って、\(x^2 -2\)のように、因数分解すると係数の一部が無理数となるものは対象としない。
まず、易しいところから、２次の多項式を考える。一般に、２次の多項式は\(p \times x^2 +q \times x+r\)と表すことができる。但し、\(p>0\)。これは因数分解できる場合には、\(a \times x + b\)と\(a' \times x + b'\)の式を得る。このとき、\(a \times a' = p\), \(a \times b' + b \times a'= q\), \(b \times b' = r\)である。
\(a \times a' = p\)と\(a\)と\(a'\)が整数であることから、\(1 \le a \le q'\)であることがわかる。そこで、\(a\)をこの範囲で動かす。この時、\(a \times a' = p\)より\(a'\)が求まるが、整数になるものだけを許す。
同様に、\(b \times b' = r\)より、\( |r| \le b \le |r| \)であることがわかる。但し、\(b\neq 0\)である。そこで、\(b\)をこの範囲で動かす。この時、\(b \times b' = r\)より\(b'\)が求まるが、やはり、整数になるものだけを許す。
最後にこのように条件の満たしたものに対し、\(a \times a' = p\), \(a \times b' + a' \times b'= q\), \(b \times b' = r\)を満たすかを調べる。このような条件を満たしたものが、因数分解した時の多項式である。
プログラムは以下のようになる。
factor2 (p:q:r:[]) = [[[a,b],[a',b']] | a <- [1..p], mod p a == 0, let a' = div p a, b <- [-abs(r)..abs(r)], b /= 0, mod r b == 0, let b' = div r b, a * b' + b * a' == q]
実行結果は次のようになる。
*Main> factor2[1,-6,8] [[[1,-4],[1,-2]],[[1,-2],[1,-4]]]
上の実行結果は、多項式の順番が違うだけで、実際は、同じものである。そこで、一つだけ得るようにプログラムを以下のように修正する。さらに、[ ] の数を一つ減らすこととする。
factor2 (p:q:r:[]) = concat $ take 1 $ [[[a,b],[a',b']] | a <- [1..p], mod p a == 0, let a' = div p a, b <- [-abs(r)..abs(r)], b /= 0, mod r b == 0, let b' = div r b, a * b' + b * a' == q]
実行結果は次のようになる。
*Main> factor2[1,-6,8] [[1,-4],[1,-2]]
