Namaran

Code daily. Without assist.

2026-10-06

Factor.hs

import Data.Array

limit :: Int
limit = 100

spf :: Array Int Int
spf = accumArray (\_ p -> p) 0 (2, limit) [(m, p) | p <- [2 .. limit], m <- [p, 2 * p .. limit]]

factor :: Int -> [Int]
factor 1 = []
factor n = p : factor (n `div` p) where p = spf ! n

main :: IO ()
main = print (map factor [12, 30, 49])

spf は2から100までの各数の最小素因数の表、factor はその表を引いて素因数を小さい順に並べるつもりの関数です。引数も標準入力も使わず、main が 12、30、49 を分解します。いまは [[12],[30],[49]] が出ます。本来は [[2,2,3],[2,3,5],[7,7]] が出るはずです。

Answer

Wrong

spf = accumArray (\_ p -> p) 0 (2, limit) [(m, p) | p <- [2 .. limit], m <- [p, 2 * p .. limit]]

accumArray f z は各添字の値を z から始め、その添字に集まった値をリストの順に f で結合します。\_ p -> p は前の値を捨てて新しい値を取るので、表に残るのはリストで最後に現れた値です。

リストは p の小さい順に作られるので、添字 12 には 2, 3, 4, 6, 12 の順に値が集まり、最後の 12 が残ります。どの添字でも最後に来るのは p = m の組なので、表のすべての数が自分自身を最小素因数として持ちます。factor 12 は 12 : factor 1 となり、[12] です。

Right

spf = accumArray min limit (2, limit) [(m, p) | p <- [2 .. limit], m <- [p, 2 * p .. limit]]

min で結合すれば、値が集まる順番に関係なく一番小さい約数が残ります。m の1より大きい最小の約数は必ず素数なので、表の値が最小素因数になります。初期値の limit は、どの添字 m にも limit 以下の p = m が集まるので、結果には残りません1。

  1. 手続き型の言語では、配列の要素がまだ0のときだけ p を書き込む形で同じ表を作ります。結合関数を \old p -> if old == 0 then p else old にすれば、accumArray でも同じ書き方になります。