2026-10-06
Quotients.hs
import Data.Array
import Data.List (unfoldr)
limit :: Int
limit = 400
spf :: Array Int Int
spf = accumArray min limit (2, limit) [(m, p) | p <- [2 .. limit], m <- [p, 2 * p .. limit]]
step :: Int -> Maybe (Int, Int)
step 1 = Nothing
step n = Just (n, n `div` spf ! n)
main :: IO ()
main = print (unfoldr step 360)
これは何を出力するでしょうか?
Answer
[360,180,90,45,15,5] です。
spf は2から400までの各数の最小素因数の表です。accumArray min は、同じ添字に集まった値を min でまとめます。添字 m には m を割り切るすべての p が集まるので、表に残るのは1より大きい最小の約数、つまり最小素因数です。
unfoldr step 360 は、step が Just (x, next) を返すたびに x をリストに並べ、next を種にして step を呼び直します。この step が並べるのは n そのものです。最小素因数の spf ! n は割る数として使われるだけで、リストには入りません1。
360 は 2 で3回割って 45、3 で2回割って 5、5 で割って 1 になります。並ぶのは種として渡った 360 から 5 までの6個で、step 1 は Nothing を返して終わるので、最後の 1 は含まれません。
n `div` spf ! nはn `div` (spf ! n)と読みます。!の優先順位は9、`div`は7なので、!が先に結び付きます。