トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ユークリッド互除法

最大公約数をもとめる手法の一つ。
自然数をm,nとするとき(m>=n)、
gcd(m,n)はmとnの剰余と小さい方の最大公約数はm,nとの最大公約数と
等しいことより、お互いの剰余と小さい方の自然数の比較を繰り返すことにより
mとnの最大公約数を得る。

javaで実装すると、

public class Test {
private int m,n;
public static void main(String[] args) {
	Test test = new Test();
	System.out.println(test.gcd(40,24));
   }
   
   public int gcd(int m,int n) {
   	int remain = 0;
   	int big = m,small = n;
   	remain = big % small;
   	while (remain > 0) {
   		big = small;
   		small = remain;
   		remain = big % small;
   	}
   	return small;
   }
}

こんな感じ。