自然语言描述
用辗转相除法确定两个正整数 a 和 b(a≥b) 的最大公因数gcd(a,b):
当a mod b=0 时gcd(a,b)=b,否则
gcd(a,b) = gcd(b,a mod b)
递归或循环运算得出结果
public final class Demo { // 功能:获取两个整数的最大公约数 // 输入:两个整数 // 返回:最大公约数 public static long getMaxDivisor(long lFirstInput, long lSecondInput) { long max=Math.max(lFirstInput, lSecondInput); long min=Math.min(lFirstInput, lSecondInput); if(max%min==0) //递归必须有结束条件 return min; return getMaxDivisor(min, max%min); //辗转相除法 } // 功能:获取两个整数的最小公倍数 // 输入:两个整数 // 返回:最小公倍数 public static long getMinMultiple(long lFirstInput, long lSecondInput) { return lFirstInput*lSecondInput/getMaxDivisor(lFirstInput, lSecondInput); } }