2020.03.23

数学

ユークリッド互除法

ここでは、与えられた2つの自然数(正の整数)の最大公約数ユークリッド互除法で求めるJavaソースコードを紹介します。

ユークリッド互除法は、以下の性質を利用して最大公約数を計算します。

等式:a = b × q + rにおいて、

"aとbの最大公約数"と"bと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ソースコード

それでは、ユークリッド互除法最大公約数を求めるJavaソースコードをみてみましょう。

GCD_3.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
public class GCD_3 {
	// 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 r = a % b;
		while ( 0 != r ) {
			a = b;
			b = r;
			r = a % b;
		}

		return b;
	}


	// メイン
	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_3.java

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

C:\talavax\javasample>javac GCD_3.java

実行

C:\talavax\javasample>java GCD_3

出力結果

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

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

Javaソースコードの解説

001
public class GCD_3 {

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

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
018
019
020
021
022
023
024
		// 最大公約数を求めるループ
		int r = a % b;
		while ( 0 != r ) {
			a = b;
			b = r;
			r = a % b;
		}

		return b;

ユークリッド互除法のメインループです。変数aをbで割った余りrが0になるまでループします。ループを抜けたときの変数bが最大公約数です。

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
	// メイン
	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

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

2020.03.23

与えられた2つの自然数の最小約数の掛け算を繰り返して最大公約数を求めるJavaソースコードを紹介しています。

2020.03.23

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

2020.03.23

割り算で割り切れずに残った端数を剰余(余り)といいます。この剰余の計算を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

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

2016.01.26

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

2016.03.02

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

2020.03.23

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

2022.12.13

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

2020.03.23

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

2020.03.23

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

2020.03.23

Javaのプログラムを作ってみませんか?プログラミングに必要なものの用意から実行までを説明しています。

2020.03.23

Swingパッケージを使ってグラフィック表示を行う方法を解説しています。

2020.03.23

繰り返し処理を使ったJavaのソースコードサンプルを紹介しています。

2020.03.23

配列を使うJavaソースコードを多数紹介しています。

2021.05.18

三角形、台形、円などいろいろな図形の面積を計算するプログラムを紹介しています。詳しくは、記事をご覧ください。

2021.05.18

StringクラスとStringBuilderクラスを利用したプログラミングの仕方を紹介しています。

2016.12.16

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

2022.08.03

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

2020.03.23

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

2020.07.08

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

2020.03.23

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

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

2020.03.23

「ゆるゆるプログラム」のコンテンツを紹介しています。興味のある方はこの記事をご覧ください。

2020.03.23

アルゴリズムって何?

2022.12.29

広告