ユークリッドの互除法を使って2つの整数の最大公約数を求める

2つの整数m、n（m > n）をユークリッドの互除法を使って、mとnの最大公約数を求めます。
減算を使った場合のアルゴリズムは次のようになります。

１．mとnが等しくないあいだは次を繰り返す
２．m > nの場合 m = m - n
　それ以外　　　 n = n - m
３．m（もしくはn）が求める最大公約数となる

これをJavaで書くと次のように書くことができます。

public class Euclid {
	public static void main(String[] args){
		try{
			int m = Integer.parseInt(args[0]);
			int n = Integer.parseInt(args[1]);
			int count = 0;
			
			while(m != n){
				if(m > n){
					m = m - n;
				}else{
					n = n - m;
				}
				count++;
			}
			System.out.println("最大公約数：" + m + ", 計算回数：" + count);			
		}catch(Exception e){
			e.printStackTrace();
		}
	}
}

ただし、上記のように減算を使った場合、mとnの差が大きいときは計算効率が悪くなる問題が考えられます。
効率を上げるには剰余を使います。剰余を用いたアルゴリズムは次のようになります。

１．mをnで割った余りをkとする
２．mにnを、nにkを入れる
３．kが0でなければ１．に戻る
４．mが求める最大公約数となる

public class Euclid {
	public static void main(String[] args){
		try{
			int m = Integer.parseInt(args[0]);
			int n = Integer.parseInt(args[1]);
			int count =0, k = 0;
			do{
				k = m % n;
				m = n;
				n = k;
				count++;
			}while(k != 0);			
			
			System.out.println("最大公約数：" + m + ", 計算回数：" + count);			
		}catch(Exception e){
			e.printStackTrace();
		}
	}
}

例として、引数に1071、81を渡して実行すると、計算効率の違いが分かると思います。

減算の場合

最大公約数：9, 計算回数：18

剰余の場合

最大公約数：9, 計算回数：3