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

「ユークリッドの互除法(2 つの自然数の最大公約数を求める)」(2012/02/09 (木) 17:14:47) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**ユークリッドの互除法

ユークリッドの互除法（ユークリッドのごじょほう）は、
2 つの自然数または整式の最大公約数を求める手法の一つです。
手順は,wikipediaの[[ユークリッドの互除法>>http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95]]に載っています。
***最大公約数 (GCD) を返す関数
もうこれは関数化しちゃってもいいですね。
 inline int gcd(int a, int b){
 	while(b > 0){
 		T r = a % b;
 		a = b;
 		b = r;
 	}
 	return a;
 }
最大公約数は再帰を使って定義することもできます。
 inline int gcd(int a, int b){
 	return (b > 0)? gcd(b, a % b) : a ;
 }
おまけ (最小公倍数 (LCM) を返す関数)
 inline int lcm(int a, int b){
 	return a / gcd(a, b) * b;
 }










...

**ユークリッドの互除法

ユークリッドの互除法（ユークリッドのごじょほう）は、
2 つの自然数または整式の最大公約数を求める手法の一つです。
詳しい説明は,wikipediaの[[ユークリッドの互除法>>http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95]]に載っています。
***最大公約数 (GCD) を返す関数
 int gcd(int a, int b){
 	return (b > 0)? gcd(b, a % b) : a ;
 }

***最小公倍数 (LCM) を返す関数
 int lcm(int a, int b){
 	return a / gcd(a, b) * b;
 }










...