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

1～10まで全てを割り切る最小の数は2520
1～20までの場合は？
Project Euler ※解法の公開は問1～100のみ可

## 考え方

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

232792560

## 末筆ながら

### ご意見求む!!

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

### スキル指標

• すごいH本
• 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です