2020/03/23 公開
・最大公約数その2
ここでは、与えられた２つの自然数（正の整数）の最大公約数を最小の約数を利用し求めるJavaソースコードを紹介します。
最大公約数を求める方法は以下の通りです。
２つの自然数を割り切れる２以上の最小公約数を求め、その約数で自然数を割ります。この計算を２以上の最小公約数が無くなるまで繰り返し行います。この計算で得られた全ての約数を掛け合わせた数が最大公約数になります。
GCD_2.java ← クリックしてダウンロードページに移動
001: public class GCD_2 {
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 ans = 1;
018:
019: // 最大公約数を求めるループ
020: for ( ; ; ) {
021: // 片方の値が1以下ならループを抜ける
022: if ( ( 1 >= a ) || ( 1 >= b ) ) break;
023:
024: // ２以上の１番小さい公約数を求める
025: int cd = 1;
026: int min= Math.min( a, b );
027: for ( int i = 2; i <= min; i ++ ) {
028: if ( 0 == ( a % i ) ) {
029: // aはiで割り切れた
030: if ( 0 == ( b % i ) ) {
031: // bはiで割り切れた
032: // 最も小さい公約数
033: cd = i;
034: break;
035: }
036: }
037: }
038:
039: // ２以上の公約数がなかったらループを抜ける
040: if ( 1 == cd ) break;
041:
042: // 最大公約数を掛け合わせる
043: ans *= cd;
044:
045: // ２つの自然数を約数で割る
046: a /= cd;
047: b /= cd;
048: }
049:
050: return ans;
051: }
052:
053:
054: // メイン
055: public static void main( String[] args ) {
056: // ２つの変数を宣言
057: int a, b;
058:
059: // ８と１２の最大公約数
060: a = 8;
061: b = 12;
062: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
063:
064: // １３と４の最大公約数
065: a = 13;
066: b = 4;
067: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
068:
069: // 144と32の最大公約数
070: a = 144;
071: b = 32;
072: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
073:
074: // ０と１０の最大公約数
075: a = 0;
076: b = 10;
077: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
078:
079: // ０と０の最大公約数
080: a = 0;
081: b = 0;
082: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
083: }
084: }
GCD_2を実行
C:\talavax\javasample>java GCD_2
実行結果
に
8と12の最大公約数は、4 13と4の最大公約数は、1 144と32の最大公約数は、16 0と10の最大公約数は、10 0と0の最大公約数は、0
正しい結果が得られています。
ここからは、このソースコードを上から順番に解説していきます。
001: public class GCD_2 {
クラス名を、GCD_2としています。
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;
012: // 片方の値が0以下なら0を戻す 013: if ( ( 0 >= a ) || ( 0 >= b ) ) 014: return Math.max( a, b );
引数a、bの片方が0以下の場合、最大公約数としてaとbの大きい値をreturn文で戻す。
016: // 最大公約数の初期値 017: int ans = 1;
019: // 最大公約数を求めるループ
020: for ( ; ; ) {
021: // 片方の値が1以下ならループを抜ける 022: if ( ( 1 >= a ) || ( 1 >= b ) ) break;
変数aとbのどちらかが１以下になったらbreak文でfor文を抜けています。
024: // ２以上の１番小さい公約数を求める 025: int cd = 1;
026: int min= Math.min( a, b );
027: for ( int i = 2; i <= min; i ++ ) {
int型の変数minにaとbの小さいほうの値を代入し、for文で２からminのループを作っています。
028: if ( 0 == ( a % i ) ) {
029: // aはiで割り切れた
030: if ( 0 == ( b % i ) ) {
031: // bはiで割り切れた
032: // 最も小さい公約数
033: cd = i;
034: break;
035: }
036: }
037: }
変数aとbを変数iで割ったときの余りが０のときに変数cdにiを代入して、break文をfor文で抜けています。
039: // ２以上の公約数がなかったらループを抜ける 040: if ( 1 == cd ) break;
変数cdが１のときにfor文で作った無限ループを抜けます。２以上の公約数が無い場合に、変数cdが１になります。
042: // 最大公約数を掛け合わせる 043: ans *= cd;
変数ansがcdに掛けています。
045: // ２つの自然数を約数で割る 046: a /= cd; 047: b /= cd;
050: return ans;
最後に、変数ansを戻しています。
054: // メイン
055: public static void main( String[] args ) {
056: // ２つの変数を宣言
057: int a, b;
058:
059: // ８と１２の最大公約数
060: a = 8;
061: b = 12;
062: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
063:
064: // １３と４の最大公約数
065: a = 13;
066: b = 4;
067: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
068:
069: // 144と32の最大公約数
070: a = 144;
071: b = 32;
072: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
073:
074: // ０と１０の最大公約数
075: a = 0;
076: b = 10;
077: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
078:
079: // ０と０の最大公約数
080: a = 0;
081: b = 0;
082: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
083: }
084: }
このmainメソッドからプログラムを実行します。最大公約数を求めるgcdメソッドに値を渡して、結果をコンソール出力しています。
■関連コンテンツ
| 最大公約数 | １番大きい約数は？ |
| 最大公約数その1 | 地道な方法 |
| 最大公約数その3 | ユークリッド互除法 |
| for文 | 繰り返し処理に使用するfor文について解説 |
| 剰余(余り)計算 | 剰余(余り)を計算した結果を表示するプログラムについて解説 |
■新着情報
| 2022.07.07 | 外部プログラムの実行 | exeファイル実行 |
| 2022.07.06 | 完全数 | ６＝１＋２＋３ |
■広告
