・0 pv・4 min read
【最小公倍数】一緒に考えませんか？ #Project Euler
考え方
素数を小さい順に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 solve232792560
考え方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]232792560
末筆ながら
ご意見求む!!
こういうStateモナドの使い方ってありなの?
Haskellerさんへ
計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします！
スキル指標
実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
- すごいH本
- 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です