【JavaScript】 最大公約数を求める

更新日：2023/06/29

JavaSciptで最大公約数を求めてみます。

 

ユークリッドの互除法で求める

最大公約数は、ユークリッドの互除法を使って求めることができます。

■参考：ユークリッドの互除法|Wikipedia

難しいことが書いてありますが、計算方法の考え方は次のようになります。

■ユークリッドの互除法の計算方法

a と b という数値があるとします。

  1. a を b で割ったときの余りを求める
  2. 余りが 0 なら、bは最大公約数
  3. 余りが 0 でないなら 現在の b を a、 余り を b として最初へ

例えば、3939 と 7777 の最大公約数を求めるとします。

  1. 3939 と 7777 の余りは、3939
  2. 7777 と 3939 の余りは、3838
  3. 3939 と 3838 の余りは、101
  4. 3838 と 101 の余りは、0

余りが 0 のときの、割る数が最大公約数です。

よって、最大公約数は 101 です。

ちなみに、このロジックでは最初の値が a > b になるのが望ましいです。
しかし実際には、順番に依存しません。

3939 と 7777 の例を見るとわかりますが、最初の割り算で余りが 3939 となり、２番目の割り算で順番が入れ替わります。
結果は、同じになるのです。

 

コード例

仕組みとしては簡単ですね。
次のようなコードで、最大公約数を求めることができます。

最大公約数計算例


const greatestCommonDivisor = ( value1 , value2 )=>{

    return value2===0 ? value1 
        : greatestCommonDivisor( value2 , value1 % value2 );

};

次のように、簡略化できます。

最大公約数計算例


const greatestCommonDivisor = ( value1 , value2 )=>
     value2===0 ? value1 
        : greatestCommonDivisor( value2 , value1 % value2 );

この例は再帰呼び出しをしているので、スタックオーバーフローが心配という人もいるかもしれません。

再帰を使用しない場合、次のようにループに置き換えることもできます。

最大公約数計算例（再帰呼び出し未使用）


const greatestCommonDivisor2 = ( value1 , value2 )=>{
    let r , a = value1 , b = value2;

    do{
        r = a % b;
        a = b;b = r;
    }while( r !== 0 );

    return a;
};

 

３つ以上の値の最大公約数

３つ以上の値の最大公約数は、まず二つの値の最大公約数を求め、その値と他の値の最大公約数を求めます。
さらにその値と他の値の最大公約数を求めることを繰り返して、最後に求めた最大公約数が全ての値の最大公約数になります。

３つ以上の値の最大公約数計算例


const greatestCommonDivisor3 = ( valueArray )=>
    valueArray.reduce( (a,b)=>greatestCommonDivisor(a,b) );

次の例のように、値は配列で渡します。

console.log(greatestCommonDivisor3([55,40,30,75]));
// 結果 : 5

 

デモ

このページに内容を元に、最大公約数を求めるツールを作成しました。

最小公倍数と最大公約数を求めるツール

更新日：2023/06/29

書いた人（管理人）：けーちゃん

関連記事

スポンサーリンク

記事の内容について

null

こんにちはけーちゃんです。
説明するのって難しいですね。

「なんか言ってることおかしくない？」
たぶん、こんなご意見あると思います。

裏付けを取りながら記事を作成していますが、僕の勘違いだったり、そもそも情報源の内容が間違えていたりで、正確でないことが多いと思います。
そんなときは、ご意見もらえたら嬉しいです。

掲載コードについては事前に動作確認をしていますが、貼り付け後に体裁を整えるなどをした結果動作しないものになっていることがあります。
生暖かい視線でスルーするか、ご指摘ください。

ご意見、ご指摘はこちら。
https://note.affi-sapo-sv.com/info.php

 

このサイトは、リンクフリーです。大歓迎です。