欧几里得算法

欧几里得算法

辗转相除法,计算两个非负整数a,b的最大公约数。
【欧几里得算法】例如24和30的最大公约数是6.
  1. 分解最小质因数
    分解 24 = 2 x 2 x 2 x 3
    分解 30 = 2 x 3 x 5
  2. 提取
    提取 2 x 3 = 6.
算法:
public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

该算法的递归过程能够自动矫正a和b的前后顺序。

    推荐阅读