Project Euler - Problem 5

問題

• 原文

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

• 日本語訳

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

解答

いきなり難易度が下がりました。人はそれを最小公倍数と呼びます。 Schemeには組み込み関数lcmがあるので、何も面白くありません。

(use srfi-1)
(define (solve)
  (apply lcm (iota 20 1)))
(define (main argv)
  (display (solve))
  (newline))

これでおしまい。せっかくなのでPerl 6版のgcd/lcm関数でも貼っておきます。

subset NonZeroInt of Int where { $_ != 0 }
sub gcd(NonZeroInt $m is copy, NonZeroInt $n is copy, NonZeroInt *@rest) {
  $m = -$m if $m < 0;
  $n = -$n if $n < 0;
  $m, $n = $n, $m if $m < $n;
  my Int $mod = $m % $n;
  my Int $gcd = $mod == 0 ?? $n !! gcd($n, $mod);
  +@rest == 0 ?? $gcd !! gcd($gcd, |@rest);
}
sub lcm(NonZeroInt $m is copy, NonZeroInt $n is copy, NonZeroInt *@rest) {
  $m = -$m if $m < 0;
  $n = -$n if $n < 0;
  my Int $lcm = $m * $n / gcd($m, $n);
  +@rest == 0 ?? $lcm !! lcm($lcm, |@rest);
}