Namaran

Code daily. Without assist.

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 を使わずに各グループの先頭を取り出せます。