2026-10-06
Factorize.hs
import Data.Array
factorize :: Array Int Int -> Int -> [(Int, Int)]
spf ! n が n の最小素因数を返す表 spf を使って、n を素因数分解する factorize を書いてください。返すのは素因数と指数の組を、素因数の小さい順に並べたリストです。n は1以上で表の範囲に収まるものとし、n が1のときは空リストを返します。入出力例の spf は2から1000までの表です。
入力例 1
factorize spf 360
出力例 1
[(2,3),(3,2),(5,1)]
入力例 2
factorize spf 97
出力例 2
[(97,1)]
入力例 3
factorize spf 1
出力例 3
[]
Reference
import Data.Array
import Data.List (group)
factorize :: Array Int Int -> Int -> [(Int, Int)]
factorize spf = runs . go
where
go 1 = []
go n = spf ! n : go (n `div` spf ! n)
runs ps = [(p, length g) | g@(p : _) <- group ps]
参考実装の go は、表で引いた最小素因数を並べながら、その素因数で割った商へ進みます。商の最小素因数はもとの数の最小素因数より小さくならないので、go 360 は [2,2,2,3,3,5] のように小さい順に並びます。同じ素因数は隣り合うので、group で連続をまとめ、各グループの先頭と長さを組にすれば指数になります。表を引けば割り切れる素数を探さずに済むので、1回の分解は、重複を含めた素因数の個数と同じ回数だけ割れば終わります。
掲載したのは参考実装で、唯一の正解ではありません。リスト内包表記の g@(p : _) は、パターンに合わない要素を黙って飛ばすので、head を使わずに各グループの先頭を取り出せます。