home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 5
最小の倍数
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
Smallest multiple
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?
まず、手計算で求めてみる
1 から 10 の最小公倍数の求め方は、
各々の素因数の最大の指数でべき乗したものをかけて
同様に
1 から 20 の最小公倍数は、
各々の素因数の最大の指数でべき乗したものをかけて
でも、これをプログラムでやろうとすると、ちょっと大変かも
なので、よく知られたユークリッドの互除法を使ってみる
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.01.19
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>
F#
更新日 : 2013.01.20
> let rec gcd a b = - if b = 0L then a else gcd b a % b - ;; val gcd : int64 -> int64 -> int64 > let lcm a b = - a * b / gcd a b - ;; val lcm : int64 -> int64 -> int64 > [1L..10L] - |> List.reduce(lcm) - ;; Process is terminated due to StackOverflowException.
> let rec gcd a b = - if b = 0L then a else gcd b (a % b) - ;; val gcd : int64 -> int64 -> int64 > let lcm a b = - a * b / gcd a b - ;; val lcm : int64 -> int64 -> int64 > [1L..10L] - |> List.reduce(lcm) - ;; val it : int64 = 2520L > [1L..20L] - |> List.reduce(lcm) - ;; val it : int64 = 232792560L >