ユークリッド互除法

2020.03.23

数学

ここでは、与えられた２つの自然数（正の整数）の最大公約数をユークリッド互除法で求める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が０になったのでa=32とb=16の最大公約数は16となります。

Javaソースコード

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

GCD_3.java

ダウンロード

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 ) {
		// ２つの変数を宣言
		int a, b;

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

		// １３と４の最大公約数
		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 ) );

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

		// ０と０の最大公約数
		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

２つの値の両方が０の場合は０を戻します。

Javaソースコードの解説

public class GCD_3 {

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

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

最大公約数を求めるメソッドgcdです。int型の２つの引数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文で戻す。

		// 最大公約数を求めるループ
		int r = a % b;
		while ( 0 != r ) {
			a = b;
			b = r;
			r = a % b;
		}

		return b;

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

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

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

		// １３と４の最大公約数
		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 ) );

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

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