Magicode logo
Magicode
0

【最小公倍数】一緒に考えませんか? #Project Euler

問5

1~10まで全てを割り切る最小の数は2520

1~20までの場合は?

Project Euler ※解法の公開は問1~100のみ可

考え方

素数を小さい順に20を越えない最大の乗数にして掛けていく

一番純粋な方法

  • 2は4つあればいい (16 = 2^4)

  • 3は2つあればいい (9 = 3^2)

  • 5は 1つでいい

  • 7 ..

  • 19 も1つでいい

素数生成

primesモジュールが使えないので簡単(非効率)に生成

primes = sieve $ 2:[3,5..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

必要な個数だけ掛けていく

素数のリストを畳込めばいい

solve :: Int
solve = foldl (\acc x -> acc * calcMiniMax20 x 1) 1 $ takeWhile (<20) primes 

20を越えない最大の乗数を求める

こういうのは再帰使わないと出来なさそう

calcMiniMax20 x n
    | n * x > 20 = n
    | otherwise = calcMiniMax20 x (x*n) 

232792560

考え方2 素数をあらかじめ定義しない方法

product [1..10] / ((2^5)*(3^2)*5) = 2520.0

product [5, 7, 8, 9] = 2520

リストから2, 3, 4, 6, 10を消せればいいという考え方

必要な値だけ連結する

リストの中身を徐々に約分して、約分できた数だけ元の値を乗算するようなイメージ

powerCons :: [Int] -> [Int]
powerCons [] = []
powerCons (x:xs) 
    | x == 1 = powerCons xs
    | otherwise = let (v, s) = runState (reduction x 1) xs in x^v : (powerCons s)

Stateモナドで管理

リストを同じ数で何度も約分していくというのを表すためのStateモナド

reduction :: Int -> Int -> State [Int] Int
reduction x n = do
    list <- gets $ map (\y -> if isDivisible x y then y `div` x else y)
    put list
    if any (isDivisible x) list
        then do
            reduction x (n+1) 
        else return n

-- 割り切れるかどうか
isDivisible :: Int -> (Int -> Bool)
isDivisible a = \b -> b `mod` a == 0

モナド練習のためだけの解法なので非効率


232792560

末筆ながら

ご意見求む!!

こういうStateモナドの使い方ってありなの?

Haskellerさんへ

計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします!

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください

読んだ本

  • すごいH本
  • 関数プログラミング実践入門 (途中)

つまり構文を知った程度で、関数型言語っぽい書き方を学び中です

Discussion

コメントにはログインが必要です。