Scala で Project Euler Problem 5
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
まず、手計算で求めてみる。
1 から 10 の最小公倍数の求め方は、
2 | 3 | 5 | 7 | |
---|---|---|---|---|
1 | ||||
2 | 1 | |||
3 | 1 | |||
4 | 2 | |||
5 | 1 | |||
6 | 1 | 1 | ||
7 | 1 | |||
8 | 3 | |||
9 | 2 | |||
10 | 1 | 1 |
同様に
1 から 20 の最小公倍数は、
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | |
---|---|---|---|---|---|---|---|---|
1 | ||||||||
2 | 1 | |||||||
3 | 1 | |||||||
4 | 2 | |||||||
5 | 1 | |||||||
6 | 1 | 1 | ||||||
7 | 1 | |||||||
8 | 3 | |||||||
9 | 2 | |||||||
10 | 1 | 1 | ||||||
11 | 1 | |||||||
12 | 2 | 1 | ||||||
13 | 1 | |||||||
14 | 1 | 1 | ||||||
15 | 1 | 1 | ||||||
16 | 4 | |||||||
17 | 1 | |||||||
18 | 1 | 2 | ||||||
19 | 1 | |||||||
20 | 2 | 1 |
でも、これをプログラムでやろうとすると、ちょっと大変かも
なので、よく知られたユークリッドの互除法を使ってみる
scala> def gcd(a: Int, b: Int): Int = | if (b == 0) a else gcd(b, a % b) gcd: (a: Int,b: Int)Int scala> scala> def lcm(a: Int, b: Int): Int = | a * b / gcd(a, b) lcm: (a: Int,b: Int)Int scala>
2と3の最小公倍数は、
scala> lcm(2,3) res0: Int = 6
2と3と4の最小公倍数は、「2と3の最小公倍数」と4の最小公倍数
scala> lcm(6,4) res1: Int = 12
2と3と4と5の最小公倍数は、「『2と3の最小公倍数』と4の最小公倍数」と5の最小公倍数...
scala> lcm(12,5) res2: Int = 60 scala> lcm(60,6) res3: Int = 60 scala> lcm(60,7) res4: Int = 420 scala> lcm(420,8) res5: Int = 840 scala> lcm(840,9) res6: Int = 2520 scala> lcm(2520,10) res7: Int = 2520
こうゆう処理には reduce が使えそうなのでやってみる
scala> (1 to 10) res0: scala.collection.immutable.Range.Inclusive with scala.collection.immutable.Range.ByOne = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) scala> scala> (1 to 10).reduceLeft(_+_) res1: Int = 55 scala> scala> (1 to 10).reduceLeft(_*_) res2: Int = 3628800 scala> scala> def gcd(a: Int, b: Int): Int = | if (b == 0) a else gcd(b, a % b) gcd: (a: Int,b: Int)Int scala> scala> def lcm(a: Int, b: Int): Int = | a * b / gcd(a, b) lcm: (a: Int,b: Int)Int scala> scala> (1 to 10).reduceLeft(lcm(_,_)) res3: Int = 2520 scala> scala> (1 to 20).reduceLeft(lcm(_,_)) res4: Int = 18044195
結果がおかしい
scala> def gcd(a: Long, b: Long): Long = | if (b == 0) a else gcd(b, a % b) gcd: (a: Long,b: Long)Long scala> scala> def lcm(a: Long, b: Long): Long = | a * b / gcd(a, b) lcm: (a: Long,b: Long)Long scala> scala> (1L to 20L).reduceLeft(lcm(_,_)) res5: Long = 232792560 scala>