Java中的数论2——gcd和lcm

Java中的GCD和LCMGCD最大公约数代码LCM最小公倍数代码GCD最大公约数又称辗转相除法。有两种实现方式代码第一种递归法更加简洁longgcd(longa,longb){if(b0)returnMath.abs(a);returngcd(b,a%b);}第二种迭代法更加高效longgcd(longa,longb){aMath.abs(a);bMath.abs(b);while(b!0){longra%b;ab;br;}returna;}其中大数类BigInteger里已经内置了gcd函数可以直接调用LCM最小公倍数与GCD的关系LCM (a,b) |a * b| / gcd (a,b);代码longlcm(longa,longb){if(a0||b0)return0;// 特殊情况longggcd(a,b);returnMath.abs(a/g*b);// 防止溢出先除再乘}