欧几里得算法
辗转相除法,计算两个非负整数a,b的最大公约数。【欧几里得算法】例如24和30的最大公约数是6.
- 分解最小质因数
分解 24 = 2 x 2 x 2 x 3
分解 30 = 2 x 3 x 5 - 提取
提取 2 x 3 = 6.
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
该算法的递归过程能够自动矫正a和b的前后顺序。
欧几里得算法
辗转相除法,计算两个非负整数a,b的最大公约数。【欧几里得算法】例如24和30的最大公约数是6.
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}