gcd算法（求最大公約數）

[size=large] gcd算法：給定倆個正整數m，n（m>=n），求它們的最大公約數。（注意，一般要求m>=n，若m<n，則要先交換m<->n。下文，會具體解釋）。以下，是此算法的具體流程：

[color=red] 1、[求餘數]，令r=m%n，r為n除m所得餘數（0<=r<n）；

2、[餘數為0?]，若r=0，算法結束，此刻，n即為所求答案，否則，繼續，轉到3；

3、[重置]，置m<-n，n<-r，傳回步驟1.[/color]

此算法的證明，可參考計算機程式設計藝術第一卷：基本算法。

ok，下面，舉一個例子，你可能看的更明朗點。

比如，給定m=544，n=119，

則餘數r=m%n=544%119=68; 因r!=0，是以跳過上述步驟2，執行步驟3。；

置m<-119，n<-68，=>r=m%n=119%68=51;

置m<-68，n<-51，=>r=m%n=68%51=17；

置m<-51，n<-17，=>r=m%n=51%17=0，算法結束，

此時的n=17，即為m=544，n=119所求的倆個數的最大公約數。

再解釋下上述gcd(m，n)算法開頭處的，要求m>=n 的原因：舉這樣一個例子，如m<n，即m=119，n=544的話，那麼r=m%n=119%544=119,

因為r!=0,是以執行上述步驟3，注意，看清楚了：m<-544，n<-119。看到了沒，盡管剛開始給的m<n，但最終執行gcd算法時，還是會把m，n的值交換過來，以保證m>=n。[/size]

/**
	 * 求最大公約數
	 * 
	 * @param m
	 * @param n
	 * @return
	 */
	public static int gcd(int m, int n)
	{
		if (m < 0 || n < 0)
		{
			System.err.println("ERROR!!");
			return -1;
		}

		while (true)
		{
			if ((m = m % n) == 0)
				return n;
			if ((n = n % m) == 0)
				return m;
		}
	}