Namaran

Code daily. Without assist.

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 は含まれません。

  1. n `div` spf ! n は n `div` (spf ! n) と読みます。! の優先順位は9、`div` は7なので、! が先に結び付きます。