24か月前公開・24か月前更新・4 min read

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

アルゴリズムHaskellProject Euler

https://cdn.magicode.io/media/notebox/889bfde8-673e-48b3-9fa5-f92bba552046.jpeg

問5

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

1～20までの場合は？

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

考え方

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

一番純粋な方法

2は４つあればいい (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)

solve :: Int
solve = foldl (\acc x -> acc * calcMiniMax20 x 1) 1 $ takeWhile (<20) primes
calcMiniMax20 :: Int -> Int -> Int
calcMiniMax20 x n
    | n * x > 20 = n
    | otherwise = calcMiniMax20 x (x*n)
primes :: [Int]
primes = sieve $ 2:[3,5..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

print solve

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

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

import Control.Monad.State

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
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

print $ product $ powerCons [1..20]