Javaプログラミング学習サイト ゆるゆるプログラミング

2020/03/23 公開

・最大公約数その2

ここでは、与えられた2つの自然数(正の整数)の最大公約数を最小の約数を利用し求めるJavaソースコードを紹介します。

最大公約数を求める方法は以下の通りです。

2つの自然数割り切れる2以上の最小公約数を求め、その約数で自然数を割ります。この計算を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:    			// 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;

引数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;

for文無限ループを作っています。

019:    		// 最大公約数を求めるループ
020:    		for ( ; ; ) {

for文無限ループを作っています。

021:    			// 片方の値が1以下ならループを抜ける
022:    			if ( ( 1 >= a ) || ( 1 >= b ) ) break;

変数aとbのどちらかが1以下になったらbreak文for文を抜けています。

024:    			// 2以上の1番小さい公約数を求める
025:    			int cd = 1;

変数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;

変数aとbを最も小さい2以上の公約数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

■広告

 

 

 

 

 

スッキリわかるJava入門第3版 [ 中山清喬 ]

価格:2,860円
(2021/6/18 14:32時点)
感想(6件)

 

 

 

 

Topへ