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

2020/07/07 公開

・最大公約数その3

ここでは、与えられた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ソースコードをみてみましょう。

GCD_3.java ← クリックしてダウンロードページに移動
001:    public class GCD_3 {
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 r = a % b;
018:    		while ( 0 != r ) {
019:    			a = b;
020:    			b = r;
021:    			r = a % b;
022:    		}
023:    
024:    		return b;
025:    	}
026:    
027:    
028:    	// メイン
029:    	public static void main( String[] args ) {
030:    		// 2つの変数を宣言
031:    		int a, b;
032:    
033:    		// 8と12の最大公約数
034:    		a = 8;
035:    		b = 12;
036:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
037:    
038:    		// 13と4の最大公約数
039:    		a = 13;
040:    		b = 4;
041:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
042:    
043:    		// 144と32の最大公約数
044:    		a = 144;
045:    		b = 32;
046:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
047:    
048:    		// 0と10の最大公約数
049:    		a = 0;
050:    		b = 10;
051:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
052:    
053:    		// 0と0の最大公約数
054:    		a = 0;
055:    		b = 0;
056:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
057:    	}
058:    }

GCD_3を実行

C:\talavax\javasample>java GCD_3

実行結果

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

正しい結果が得られています。

001:    public class GCD_3 {

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

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 r = a % b;
018:    		while ( 0 != r ) {
019:    			a = b;
020:    			b = r;
021:    			r = a % b;
022:    		}
023:    
024:    		return b;

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

028:    	// メイン
029:    	public static void main( String[] args ) {
030:    		// 2つの変数を宣言
031:    		int a, b;
032:    
033:    		// 8と12の最大公約数
034:    		a = 8;
035:    		b = 12;
036:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
037:    
038:    		// 13と4の最大公約数
039:    		a = 13;
040:    		b = 4;
041:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
042:    
043:    		// 144と32の最大公約数
044:    		a = 144;
045:    		b = 32;
046:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
047:    
048:    		// 0と10の最大公約数
049:    		a = 0;
050:    		b = 10;
051:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
052:    
053:    		// 0と0の最大公約数
054:    		a = 0;
055:    		b = 0;
056:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
057:    	}
058:    }

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

■関連コンテンツ

最大公約数 1番大きい約数は?
最大公約数その1 地道な方法
最大公約数その2 2以上の最も小さい約数を利用
for文 繰り返し処理に使用するfor文について解説
剰余(余り)計算 剰余(余り)を計算した結果を表示するプログラムについて解説

■新着情報

2021.06.23 配列の初期値 配列の生成直後の値は?
2021.06.18 変数の初期値 変数に値を代入しないで計算

■広告

 

 

 

 

 

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

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

 

 

 

 

Topへ