2020/03/23 公開
・最大公約数その2
ここでは、与えられた2つの自然数(正の整数)の最大公約数を最小の約数を利用し求めるJavaソースコードを紹介します。
最大公約数を求める方法は以下の通りです。
2つの自然数を割り切れる2以上の最小公約数を求め、その約数で自然数を割ります。この計算を2以上の最小公約数が無くなるまで繰り返し行います。この計算で得られた全ての約数を掛け合わせた数が最大公約数になります。
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: // 2以上の1番小さい公約数を求める 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: // 2以上の公約数がなかったらループを抜ける 040: if ( 1 == cd ) break; 041: 042: // 最大公約数を掛け合わせる 043: ans *= cd; 044: 045: // 2つの自然数を約数で割る 046: a /= cd; 047: b /= cd; 048: } 049: 050: return ans; 051: } 052: 053: 054: // メイン 055: public static void main( String[] args ) { 056: // 2つの変数を宣言 057: int a, b; 058: 059: // 8と12の最大公約数 060: a = 8; 061: b = 12; 062: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 063: 064: // 13と4の最大公約数 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: // 0と10の最大公約数 075: a = 0; 076: b = 10; 077: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 078: 079: // 0と0の最大公約数 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型の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;
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のどちらかが1以下になったらbreak文でfor文を抜けています。
024: // 2以上の1番小さい公約数を求める 025: int cd = 1;
026: int min= Math.min( a, b ); 027: for ( int i = 2; i <= min; i ++ ) {
int型の変数minにaとbの小さいほうの値を代入し、for文で2から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で割ったときの余りが0のときに変数cdにiを代入して、break文をfor文で抜けています。
039: // 2以上の公約数がなかったらループを抜ける 040: if ( 1 == cd ) break;
変数cdが1のときにfor文で作った無限ループを抜けます。2以上の公約数が無い場合に、変数cdが1になります。
042: // 最大公約数を掛け合わせる 043: ans *= cd;
変数ansがcdに掛けています。
045: // 2つの自然数を約数で割る 046: a /= cd; 047: b /= cd;
050: return ans;
最後に、変数ansを戻しています。
054: // メイン 055: public static void main( String[] args ) { 056: // 2つの変数を宣言 057: int a, b; 058: 059: // 8と12の最大公約数 060: a = 8; 061: b = 12; 062: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 063: 064: // 13と4の最大公約数 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: // 0と10の最大公約数 075: a = 0; 076: b = 10; 077: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 078: 079: // 0と0の最大公約数 080: a = 0; 081: b = 0; 082: System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) ); 083: } 084: }
このmainメソッドからプログラムを実行します。最大公約数を求めるgcdメソッドに値を渡して、結果をコンソール出力しています。
■関連コンテンツ
最大公約数 | 1番大きい約数は? |
最大公約数その1 | 地道な方法 |
最大公約数その3 | ユークリッド互除法 |
for文 | 繰り返し処理に使用するfor文について解説 |
剰余(余り)計算 | 剰余(余り)を計算した結果を表示するプログラムについて解説 |
■新着情報
2022.07.07 | 外部プログラムの実行 | exeファイル実行 |
2022.07.06 | 完全数 | 6=1+2+3 |
■広告
