Scala で Project Euler Problem 5

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

http://projecteuler.net/problem=5

まず、手計算で求めてみる。
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>