2020/07/07 公開
・最大公約数その3
ここでは、与えられた２つの自然数（正の整数）の最大公約数をユークリッド互除法で求めるJavaソースコードを紹介します。
ユークリッド互除法は、以下の性質を利用して最大公約数を計算します。
等式：a = b × q + rにおいて、
例として、a = 144、b = 32の場合を考えてみます。
等式：a = b × q + rに値を代入すると、
144 = 32 × q + r
整数のqとrを求めると
q = 4
r = 16
となります。
bをa、rをbにし、等式に代入すると
a = 32
b = 16
となり、等式は
32 = 16 × q + r
となります。
整数のqとrを求めると
q = 2
r = 0
となります。余りrが０になったのでa=32とb=16の最大公約数は16となります。
それでは、ユークリッド互除法で最大公約数を求めるJavaソースコードをみてみましょう。
GCD_3.java ← クリックしてダウンロードページに移動
001: public class GCD_3 {
002: // aとbの最大公倍数を戻すメソッド
003: // 値が取得できない場合0を戻す
004: static int gcd( int a, int b )
005: {
006: // 両方の値が0以下なら0を戻す
007: if ( ( 0 >= a ) && ( 0 >= b ) ) return 0;
008:
009: // 両方の値が同じならaを戻す
010: if ( a == b ) return a;
011:
012: // 片方の値が0以下なら0を戻す
013: if ( ( 0 >= a ) || ( 0 >= b ) )
014: return Math.max( a, b );
015:
016: // 最大公約数を求めるループ
017: int r = a % b;
018: while ( 0 != r ) {
019: a = b;
020: b = r;
021: r = a % b;
022: }
023:
024: return b;
025: }
026:
027:
028: // メイン
029: public static void main( String[] args ) {
030: // ２つの変数を宣言
031: int a, b;
032:
033: // ８と１２の最大公約数
034: a = 8;
035: b = 12;
036: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
037:
038: // １３と４の最大公約数
039: a = 13;
040: b = 4;
041: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
042:
043: // 144と32の最大公約数
044: a = 144;
045: b = 32;
046: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
047:
048: // ０と１０の最大公約数
049: a = 0;
050: b = 10;
051: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
052:
053: // ０と０の最大公約数
054: a = 0;
055: b = 0;
056: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
057: }
058: }
GCD_3を実行
C:\talavax\javasample>java GCD_3
実行結果
8と12の最大公約数は、4 13と4の最大公約数は、1 144と32の最大公約数は、16 0と10の最大公約数は、10 0と0の最大公約数は、0
正しい結果が得られています。
001: public class GCD_3 {
クラス名を、GCD_3としています。
002: // aとbの最大公倍数を戻すメソッド
003: // 値が取得できない場合0を戻す
004: static int gcd( int a, int b )
005: {
最大公約数を求めるメソッドgcdです。int型の２つの引数a、bを渡して、aとbを割り切れる最大の値を求めるメソッドです。その中で一番大きい値を返すメソッドです。
006: // 両方の値が0以下なら0を戻す 007: if ( ( 0 >= a ) && ( 0 >= b ) ) return 0;
引数a、bの両方が0以下の場合、最大公約数は無いのでreturn文で0を戻しています。
009: // 両方の値が同じならaを戻す 010: if ( a == b ) return a;
引数a、bが同じの場合、return文でaを戻しています。
012: // 片方の値が0以下なら0を戻す 013: if ( ( 0 >= a ) || ( 0 >= b ) ) 014: return Math.max( a, b );
引数a、bの片方が0以下の場合、最大公約数としてaとbの大きい値をreturn文で戻す。
016: // 最大公約数を求めるループ
017: int r = a % b;
018: while ( 0 != r ) {
019: a = b;
020: b = r;
021: r = a % b;
022: }
023:
024: return b;
ユークリッド互除法のメインループです。変数aをbで割った余りrが0になるまでループします。ループを抜けたときの変数bが最大公約数です。
028: // メイン
029: public static void main( String[] args ) {
030: // ２つの変数を宣言
031: int a, b;
032:
033: // ８と１２の最大公約数
034: a = 8;
035: b = 12;
036: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
037:
038: // １３と４の最大公約数
039: a = 13;
040: b = 4;
041: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
042:
043: // 144と32の最大公約数
044: a = 144;
045: b = 32;
046: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
047:
048: // ０と１０の最大公約数
049: a = 0;
050: b = 10;
051: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
052:
053: // ０と０の最大公約数
054: a = 0;
055: b = 0;
056: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
057: }
058: }
このmainメソッドからプログラムを実行します。最大公約数を求めるgcdメソッドに値を渡して、結果をコンソール出力しています。
■関連コンテンツ
| 最大公約数 | １番大きい約数は？ |
| 最大公約数その1 | 地道な方法 |
| 最大公約数その2 | ２以上の最も小さい約数を利用 |
| for文 | 繰り返し処理に使用するfor文について解説 |
| 剰余(余り)計算 | 剰余(余り)を計算した結果を表示するプログラムについて解説 |
■新着情報
| 2021.06.23 | 配列の初期値 | 配列の生成直後の値は？ |
| 2021.06.18 | 変数の初期値 | 変数に値を代入しないで計算 |
■広告
