计算两个数的最大公因子_JAVA_编程开发_程序员俱乐部

?

给定两个正整数m和n，求它们的最大公因子，即能够同时整除m和n的最大正整数。

E1.【求余数】 以n除m并令r为所得余数。（我们将有0<=r<n）

E2.【余数为零？】若r=0,算法结束，n即为答案。

E3.【减少】置m?---n,n?-r,并返回步骤E1

?

?

package com.javaeye.rsrt;

/**
 * @description 求两个数的最大公因子
 * @author nishiting
 * @date 2010-9-15
 */
public class CommonFactor {

	/**
	 * @param arags
	 */
	public static int result=0;
	public static void main(String[] args) {

		int a = 77;
		int b = 21;
		
		CommonFactor cf = new CommonFactor();
		cal c = cf.new cal();
		c.calculate(a, b);
		System.out.println(a + "与" + b + "的最大公因子为：" + ((Integer)result).toString());
	}

	private class cal {

		public cal() {

		}

		public void calculate(int a, int b) {

			// 如果a比b小，那么a与b交换
			if (a < b) {
				int temp = a;
				a = b;
				b = temp;
			}

			if (a % b == 0) {
				result = b;
			} else {
				int r = a % b;
				a = b;
				b = r;
				calculate(a, b);
			}
		}
	}

}