如何用Java求两个任意数的最大公约数

知识点：

• 最大公约数：公约数，亦称“公因数”。它是一个能被若干个整数同时均整除的整数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”；公约数中最大的称为最大公约数(H.C.F. / G.C.D.)

• 计算两个非负整数p和q的最大公约数：
  若q是0，则最大公约数为p
  否则，将p除以q得到余数r
  p和q的最大公约数即为q和r的最大公约数

代码实现

package tv.zhangjia.algorithms;

public class Test {
	public int gcd(int p, int q) {
		if(q == 0) {
			return p;
		}
		int r = p % q;
		return gcd(q,r);
	}
	
	public static void main(String[] args) {
		int gcd = new Test().gcd(18, 30);
		System.out.println("18和30的最大公约数为：" + gcd);//输出6
	}
}

参考资料

algorithms 4th edition