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

2020/03/23 公開

・最大公約数その1

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

最大公約数を求める方法は、2つの自然数の小さい数から1ずつ減らしていき、2つの自然数を割り切った値を最大公約数とする方法です。

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

GCD_1.java ← クリックしてダウンロードページに移動
001:    public class GCD_1 {
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:    		// aとbの小さい値をminに代入
013:    		int min = Math.min( a, b );
014:    
015:    		// 最大公約数の初期値を代入
016:    		int ans = 1;
017:    
018:    		// 最大公約数を求めるループ
019:    		for ( int i = min; i >= 2; i -- ) {
020:    			if ( 0 == ( a % i ) ) {
021:    				// aはiで割り切れた
022:    				if ( 0 == ( b % i ) ) {
023:    					// bはiで割り切れた
024:    					// iが最大公約数
025:    					ans = i;
026:    					break;
027:    				}
028:    			}
029:    		}
030:    
031:    		// 最大公約数を戻す
032:    		return ans;
033:    	}
034:    
035:    
036:    	// メイン
037:    	public static void main( String[] args ) {
038:    		// 2つの変数を宣言
039:    		int a, b;
040:    
041:    		// 8と12の最大公約数
042:    		a = 8;
043:    		b = 12;
044:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
045:    
046:    		// 13と4の最大公約数
047:    		a = 13;
048:    		b = 4;
049:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
050:    
051:    		// 144と32の最大公約数
052:    		a = 144;
053:    		b = 32;
054:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
055:    
056:    		// 0と10の最大公約数
057:    		a = 0;
058:    		b = 10;
059:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
060:    
061:    		// 0と0の最大公約数
062:    		a = 0;
063:    		b = 0;
064:    		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
065:    	}
066:    }

GCD_1を実行

C:\talavax\javasample>java GCD_1

実行結果

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

正しい結果が得られています。法にユークリッド互除法があります。一般的に

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

001:    public class GCD_1 {

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

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:    		// aとbの小さい値をminに代入
013:    		int min = Math.min( a, b );
014:    
015:    		// 最大公約数の初期値を代入
016:    		int ans = 1;
017:    
018:    		// 最大公約数を求めるループ
019:    		for ( int i = min; i >= 2; i -- ) {
020:    			if ( 0 == ( a % i ) ) {
021:    				// aはiで割り切れた
022:    				if ( 0 == ( b % i ) ) {
023:    					// bはiで割り切れた
024:    					// iが最大公約数
025:    					ans = i;
026:    					break;
027:    				}
028:    			}
029:    		}

int型変数minにaとbの小さいほうの値を代入します。変数iをminから2まで1ずつ減らしていき、aとbの両方が割り切れたときの変数iの値をansに代入し、break文for文を抜けます。

031:    		// 最大公約数を戻す
032:    		return ans;

最後に変数ansをreturn文で戻します。割り切れる数がない場合、ans=1を戻します。

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

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

■関連コンテンツ

最大公約数 1番大きい約数は?
最大公約数その2 2以上の最も小さい約数を利用
最大公約数その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へ