最大公約数を求めるユークリッドの互除法（GCM）

2020-08-26

こんにちは、0371です。

今回は、ユークリッドの互除法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。

ユークリッドの互除法 とは

二つの整数の大きい数値から小さい数値を引き続け、両者が等しくなるまで繰り返す。
等しくなった値が最大公約数。

GCMは、Greatest Common Measure（最大公約数）の頭文字が由来になっている。

コード

今回は、二つの整数から最大公約数を求めます。 言語はJavaです。

main関数内の変数 a と b に好きな数値を当てはめてください。
int型の最大値は、2147483647 2の31乗なので、それよりも下の数値にしましょう。

※なぜ32ではなく31乗なのかというと、最上位のビット(左端のビット)は符号ビットとして使われているためです。
2の補数で表すと、0は+、1は-となります。

Main.java

public class Main {

	public static void main(String[] args) {
		int a = 84; // ここに好きな数値をいれる
		int b = 24; // ここに好きな数値をいれる
		System.out.println(a+" と "+b+" の最大公約数は "+GCP(a,b));
	}

	private static int GCP(int a, int b) {
		int count = 0; // 確認用
		while(a != b) {
			count++; // 確認用
			System.out.println(count+"回目の処理"); // 確認用
			
			if(a > b) {
				System.out.println("a = "+a+ " - " +b); // 確認用
				a = a - b;
			} else {
				System.out.println("b = "+b+ " - " +a); // 確認用
				b = b - a;
			}

			System.out.println("a = "+a); // 確認用
			System.out.println("b = "+b); // 確認用
			System.out.println(); // 確認用
		}
		return a;
	}
}

確認用とコメントしている行は、削除しても構いません。
トレースする場合はそのまま実行してください。

上記の設定した数値で実行すると、以下のような結果が表示されます。

1回目の処理
a = 84 - 24
a = 60
b = 24

2回目の処理
a = 60 - 24
a = 36
b = 24

3回目の処理
a = 36 - 24
a = 12
b = 24

4回目の処理
b = 24 - 12
a = 12
b = 12
84 と 24 の最大公約数は 12

ちなみに、whileループではなく、再帰処理で記述した場合はこうなります。

Main.java

public class Main {

	public static void main(String[] args) {
		int a = 84;
		int b = 24;
		System.out.println(a+" と "+b+" の最大公約数は "+GCP(a,b));
	}

	private static int GCP(int a, int b) {

		if(a > b) {
			a = a - b;
		} else {
			b = b - a;
		}

		if(a != b) {
			return GCP(a,b);
		}
		return a;
	}
}

結果は一つ目のコードと同じです。

今日の一言

アルゴリズム、わからん。