首页 > 代码库 > [算法]辗转相除法求最大公约数

[算法]辗转相除法求最大公约数

辗转相除法用得比较多,今天Mark一下。具体做法就是:如果q和r分别是m除以n的商及余数,即m=nq+r,那么m和n的最大公约数等于n和r的最大公约数。

代码如下:

public static int gcd(int m, int n) {
    return n == 0 ? m : gcd(n, m % n);
}

 

[算法]辗转相除法求最大公约数