Java求最大公约数（带算法详细解释）

关键代码

/**
     * 其中a > b
     * @param a
     * @param b
     * @return
     */
    public static int maxDivisor(int a, int b){
        int n = a;
        int m = b;
        int r = 0;
        while(m!=0){
            r = n%m;
            n = m;
            m = r;
        }
        return n;
    }

证明：两个数的最大公约数 等于 两个数的余数和小的整数的 最大公约数

假设a、b的最大公约数为d（a > b）,其中a % b = r（r > 0）,求证b、r的最大公约数也是d
证明过程
因为a、b的最大公约数为d，故a = xd、b = yd；
因为a % b = r，故a = zb + r，故a = yzd + r = xd，故r = (x - yz)d，即r整除d；
故d时b、r的约数。下面证明约数的范围。

假设b、r有约数g，则 b = ng、r = mg，则a = zng + mg = (zn + m)g，则g也是a、b的约数；
由于a、b的最大公约数为d，故g <= d，所以b、r最大公约数为d

结论

代码中m==0时，可以知道前一个循环中n % m = 0，即可以整除了，m 是 此循环中m、n的最大公约数，也是最初的m、n的最大公约数

最后

以上就是飘逸乐曲为你收集整理的Java求最大公约数（带算法详细解释）的全部内容，希望文章能够帮你解决Java求最大公约数（带算法详细解释）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。