「ユークリッドの互除法(2 つの自然数の最大公約数を求める)」の編集履歴（バックアップ）一覧に戻る

ユークリッドの互除法(2 つの自然数の最大公約数を求める) - (2010/06/15 (火) 21:59:24) の編集履歴(バックアップ)

---

ユークリッドの互除法

ユークリッドの互除法（ユークリッドのごじょほう）は、
2 つの自然数または整式の最大公約数を求める手法の一つです。
手順は,wikipediaのユークリッドの互除法に載っています。

手順どおり素直にコーディングするだけで最大公約数を求めるプログラムができます。
以下にプログラム例を載せます。

/***ユークリッドの互除法***/
#include <stdio.h>

int main(void){
	int m, n, a;

	while(1){
		printf("数値m,nの入力:");
		scanf("%d %d", &m, &n);
		if(n==0 && m==0) break;

		if(m<=n){//nの方が大きかったら数値を交換する
			a = m;
			m = n;
			n = a;
		}
		while(1){//解が求まるまで繰り返す
			if(n==0){//nが0ならmが解である
				printf("\n2つの数字の最大公約数は%dです!\n", m);
				break;
			}
			if(n%m==0){//nがmで割り切れたらnが解である
				printf("\n2つの数字の最大公約数は%dです\n", n);
				break;
			}
			a = m%n;  //mをnで割った余りを求める(一時的にaにいれる)
			m = n;    //元のnをmに入れる
			n = a;    //上で求めた余りをnに入れる
		}
	}
	return 0;
}

...

最大公約数 (GCD) を返す関数

もうこれは関数化しちゃってもいいですね。

template <typename T>
T gcd(T a, T b){
	T r;
	while(b > 0){
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

最大公約数は再帰を使って定義することもできます。

template <typename T> T gcd(T a, T b){
	int r;
	return ((r = a % b) == 0)
		? b
		: gcd(b, r);
}

おまけ (最小公倍数 (LCM) を返す関数)

template <typename T>
T lcm(T a, T b){
	return (a > 0 && b > 0)
		? a / gcd(a, b) * b
		: -1;
}