Javascriptで最大公約数を求める(ユークリッドの互除法)

今回は、数学的なお話。ユークリッドの互除法をJavascriptでしてみようと思います。

まず...
ユークリッドの互除法とは?という方へ。

ユークリッドの互除法は、簡単に最大公約数を求めるための計算法です。説明より例を示した方がいいかと思いますので、例題を一つ。
(例題) 1071と1029の最大公約数を求めよ。

• 1071 を 1029 で割った余りは 42
• 1029 を 42 で割った余りは 21
• 42 を 21 で割った余りは 0
• よって、答えは 42

では、これをプログラムに書き起こしてみましょう。関数名は最大公約数の略であるG. C. D.としました。

function gcd(m, n) {
  // 剰余
  var r;

  if(m < n) {  // m >= nにする
    r = m;  //一時退避
    m = n;
    n = r;
  }

  while ((r = m % n) != 0) {
    m = n;
    n = r;
  }

  return n;
}