Haskellで素因数分解

Web上で色々と探してみて、一番コードが分かりやすかったのがこれ。

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さんのブログ

factorsで約数のリストを作り、factorizationでは約数のリストから小さい順に割っていくことで素因数のリストを作っていき、1になったら終了する。

ある程度の数まではこれで十分だが、素因数となる数が大きくなると、実行が極端に遅くなってしまうのが難点。

Prelude> :set +s
Prelude> factorization 600851475143
[71,839,1471,6857]
(0.02 secs, 0 bytes)
Prelude> factorization 60085147514
[2,7,17,23,10976461]
(8.77 secs, 1758291584 bytes)
Prelude> factorization 6008514751434
[2,3,13,17,Interrupted. (1分待っても返ってこなかったので強制停止)

もう少し探してみると、Data.Numbers.Primesパッケージの中に、primeFactorsと言うまさにそのものな関数を発見したので、試してみる。

Prelude> import Data.Numbers.Primes
(0.00 secs, 0 bytes)
Prelude Data.Numbers.Primes> primeFactors 600851475143
Loading package primes-0.2.1.0 ... linking ... done.
[71,839,1471,6857]
(0.00 secs, 0 bytes)
Prelude Data.Numbers.Primes> primeFactors 60085147514
[2,7,17,23,10976461]
(0.00 secs, 5722632 bytes)
Prelude Data.Numbers.Primes> primeFactors 6008514751434
[2,3,13,17,4531308259]
(0.00 secs, 28296040 bytes)

は、速い。。。 典型的な処理は、まずパッケージをあたってみるのが良さそう。