2020/07/07 公開
・最大公約数その3
ここでは、与えられた2つの自然数(正の整数)の最大公約数をユークリッド互除法で求める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が0になったので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: // 2つの変数を宣言 031: int a, b; 032: 033: // 8と12の最大公約数 034: a = 8; 035: b = 12; 036: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 037: 038: // 13と4の最大公約数 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: // 0と10の最大公約数 049: a = 0; 050: b = 10; 051: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 052: 053: // 0と0の最大公約数 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型の2つの引数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: // 2つの変数を宣言 031: int a, b; 032: 033: // 8と12の最大公約数 034: a = 8; 035: b = 12; 036: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 037: 038: // 13と4の最大公約数 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: // 0と10の最大公約数 049: a = 0; 050: b = 10; 051: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 052: 053: // 0と0の最大公約数 054: a = 0; 055: b = 0; 056: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 057: } 058: }
このmainメソッドからプログラムを実行します。最大公約数を求めるgcdメソッドに値を渡して、結果をコンソール出力しています。
■関連コンテンツ
最大公約数 | 1番大きい約数は? |
最大公約数その1 | 地道な方法 |
最大公約数その2 | 2以上の最も小さい約数を利用 |
for文 | 繰り返し処理に使用するfor文について解説 |
剰余(余り)計算 | 剰余(余り)を計算した結果を表示するプログラムについて解説 |
■新着情報
2021.12.21 | 現在の日時を取得 | いまの年月日、時分秒? |
■広告
