博客

此算法的证明，可参考计算机程序设计艺术第一卷：基本算法。

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;
		}
	}