2020.03.23

数学

最大公約数 その2

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

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

2つの自然数割り切れる2以上の最小公約数を求め、その約数で自然数を割ります。この計算を2以上の最小公約数が無くなるまで繰り返し行います。この計算で得られた全ての約数を掛け合わせた数が最大公約数になります。

Javaソースコード

それでは、Javaソースコードをみてみましょう。

GCD_2.java

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
public class GCD_2 {
	// aとbの最大公倍数を戻すメソッド
	// 値が取得できない場合0を戻す
	static int gcd( int a, int b )
	{
		// 両方の値が0以下なら0を戻す
		if ( ( 0 >= a ) && ( 0 >= b ) ) return 0;

		// 両方の値が同じならaを戻す
		if ( a == b ) return a;

		// 片方の値が0以下なら0を戻す
		if ( ( 0 >= a ) || ( 0 >= b ) )
			return Math.max( a, b );

		// 最大公約数の初期値
		int ans = 1;

		// 最大公約数を求めるループ
		for ( ; ; ) {
			// 片方の値が1以下ならループを抜ける
			if ( ( 1 >= a ) || ( 1 >= b ) ) break;

			// 2以上の1番小さい公約数を求める
			int cd = 1;
			int min= Math.min( a, b );
			for ( int i = 2; i <= min; i ++ ) {
				if ( 0 == ( a % i ) ) {
					// aはiで割り切れた
					if ( 0 == ( b % i ) ) {
						// bはiで割り切れた
						// 最も小さい公約数
						cd = i;
						break;
					}
				}
			}

			// 2以上の公約数がなかったらループを抜ける
			if ( 1 == cd ) break;

			// 最大公約数を掛け合わせる
			ans *= cd;

			// 2つの自然数を約数で割る
			a /= cd;
			b /= cd;
		}

		return ans;
	}


	// メイン
	public static void main( String[] args ) {
		// 2つの変数を宣言
		int a, b;

		// 8と12の最大公約数
		a = 8;
		b = 12;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 13と4の最大公約数
		a = 13;
		b = 4;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 144と32の最大公約数
		a = 144;
		b = 32;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 0と10の最大公約数
		a = 0;
		b = 10;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 0と0の最大公約数
		a = 0;
		b = 0;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
	}
}

コンパイル ソースコードが「ANSI」の場合

C:\talavax\javasample>javac -encoding sjis GCD_2.java

コンパイル ソースコードが「UTF-8」の場合

C:\talavax\javasample>javac GCD_2.java

実行

C:\talavax\javasample>java GCD_2

出力結果

8と12の最大公約数は、4
13と4の最大公約数は、1
144と32の最大公約数は、16
0と10の最大公約数は、10
0と0の最大公約数は、0

2つの値の両方が0の場合は0を戻します。

Javaソースコードの解説

ここからは、このソースコードを上から順番に解説していきます。

001
public class GCD_2 {

クラス名を、GCD_2としています。

002
003
004
005
	// aとbの最大公倍数を戻すメソッド
	// 値が取得できない場合0を戻す
	static int gcd( int a, int b )
	{

最大公約数を求めるメソッドgcdです。int型の2つの引数a、bを渡して、aとbを割り切れる最大の値を求めるメソッドです。

その中で一番大きい値を返すメソッドです。

006
007
		// 両方の値が0以下なら0を戻す
		if ( ( 0 >= a ) && ( 0 >= b ) ) return 0;

引数a、bの両方が0以下の場合、最大公約数は無いのでreturn文で0を戻します。

009
010
		// 両方の値が同じならaを戻す
		if ( a == b ) return a;

引数a、bが同じの場合、return文でaを戻します。

012
013
014
		// 片方の値が0以下なら0を戻す
		if ( ( 0 >= a ) || ( 0 >= b ) )
			return Math.max( a, b );

引数a、bの片方が0以下の場合、最大公約数としてaとbの大きい値をreturn文で戻す。

016
017
		// 最大公約数の初期値
		int ans = 1;

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

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

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

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

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

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

変数cdに最も小さい公約数の初期値1を代入します。

026
027
			int min= Math.min( a, b );
			for ( int i = 2; i <= min; i ++ ) {

int型変数minにaとbの小さいほうの値を代入し、for文で2からminのループを作っています。

028
029
030
031
032
033
034
035
036
037
				if ( 0 == ( a % i ) ) {
					// aはiで割り切れた
					if ( 0 == ( b % i ) ) {
						// bはiで割り切れた
						// 最も小さい公約数
						cd = i;
						break;
					}
				}
			}

変数aとbを変数iで割ったときの余りが0のときに変数cdにiを代入して、break文for文で抜けています。

039
040
			// 2以上の公約数がなかったらループを抜ける
			if ( 1 == cd ) break;

変数cdが1のときにfor文で作った無限ループを抜けます。2以上の公約数が無い場合に、変数cdが1になります。

042
043
			// 最大公約数を掛け合わせる
			ans *= cd;

変数ansがcdに掛けています。

045
046
047
			// 2つの自然数を約数で割る
			a /= cd;
			b /= cd;

変数aとbを最も小さい2以上の公約数cdで割っています。

050
		return ans;

最後に、変数ansを戻しています。

054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
	// メイン
	public static void main( String[] args ) {
		// 2つの変数を宣言
		int a, b;

		// 8と12の最大公約数
		a = 8;
		b = 12;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 13と4の最大公約数
		a = 13;
		b = 4;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 144と32の最大公約数
		a = 144;
		b = 32;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 0と10の最大公約数
		a = 0;
		b = 10;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 0と0の最大公約数
		a = 0;
		b = 0;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
	}
}

このmainメソッドからプログラムを実行します。最大公約数を求めるgcdメソッドに値を渡して、結果をコンソール出力しています。

以上です。

関連コンテンツ

数学に関係するJavaのメソッドやソースコードなどを紹介しています。

2022.10.25

最大公約数について解説しています。興味がある方はご覧ください。

2020.07.08

与えられた2つの自然数の最大公約数を地道に求めるJavaソースコードを紹介しています。

2020.03.23

ユークリッドの互除法による最大公約数の求め方を解説しています。Javaのソース付きです。

2020.03.23

処理を繰り返すために使用するfor文について解説しています。

2020.03.23

繰り返し処理の作り方を解説しています。

2016.03.02

割り算で割り切れずに残った端数を剰余(余り)といいます。この剰余の計算をJavaのソースコードを使って解説しています。

2020.03.23

Javaの学習に役立つソースコードを多数紹介しています。是非、ご覧ください。

2022.09.10

Javaを使った簡単な応用プログラム(生年月日から年齢を計算プログラムなど)を紹介しています。

2022.07.07

日本で使われてきた伝統文様「和柄」について解説しています。

2022.07.27

画像フォーマット形式・色・大きさ・傾きなどの変更、特定の図形(文字・記号など)を見つけたり、取り出したりする画像処理について詳しく解説。

2015.11.29

プログラミング、ITに関する用語をまとめています。

2022.10.17

条件式を判断して処理を分岐する方法を詳しく説明しています。

2023.03.20

メソッドを抜けるときに使用するreturn文について説明しています。

2020.03.20

繰り返し処理(ループ)から強制的に抜けかたについて解説しています。

2017.07.14

変数やクラスに格納されている値をコンソール出力する方法は?

2020.03.23

プログラムの最初に実行されるメソッドは?

2022.12.13

プログラミングで使う変数って何?

2020.03.23

Javaのプログラムを書いてみませんか?プログラムの書き方をくわしく説明しています。

2020.03.23

「Javaソースコード」から実行可能な「オブジェクトコード」に変換する方法をくわしく説明しています。

2020.03.23

プログラミング言語とは?種類や特徴について説明しています。

2022.08.03

自然数と整数って何が違う?

2020.03.23

割り算で「割り切れる」、「割り切れない」ってどういうこと?

公約数について解説しています。興味がある方はご覧ください。

2020.07.08

Javaプログラムの構成について解説しています。詳しくは、こちらをご覧ください。

2020.03.23

メソッドの定義方法を詳しく解説しています。Javaのサンプルソースコードを使った説明もあります。

2020.03.23

for文で変数名iがよく使われる理由について説明しています。興味のある方は是非。

2022.08.29

広告