Java实现：求两个数的最大公约数

title: Java实现：求两个数的最大公约数

tags:

• java
• 算法

  categories: 个人笔记

  copyright: true

  abbrlink: f202

  date: 2019-12-07 16:44:58

求解两个数的最大公约数的几种方法的比较

1. 暴力枚举法

• 优点：思路简单

• 缺点：运算次数多，效率低

• 极端例子：求1000和10001的最大公约数

  需要计算1000/2 - 1 = 4999次

 // 暴力枚举法
        public static int getGreatestCommonDivisor(int a,int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        for (int i = small / 2; i > 1; i--) {
            if (big % i == 0 && small % i == 0) {
                return i;
            }
        }
        return 1;
    }

2. 辗转相除法

• 优点：运算次数少
• 确定：模运算的开销较大

    // 辗转相除法
    public static int getGreatestCommonDivisor2(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor2(big % small, small);
    }

3. 更相减损法

• 优点：避免了取模运算，采用减法运算，开销较小
• 缺点：算法性能不稳定，运算次数多
• 极端例子：两数相差悬殊时，如求1和10001的最大公约数，需要递归9999次

    // 更相减损法
    public static int getGreatestCommonDivisor3(int a, int b) {
        if(a == b){
            return a;
        }
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        return getGreatestCommonDivisor2(big - small, small);
    }

4. 结合辗转相除法和更相减损法（位运算优化）

当a和b均为偶数时，gcd(a,b) = 2×gcd(a/2,b/2) = 2×gcd(a >>１，ｂ＞＞１)。

当a为偶数，b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a >>１，ｂ)。

当a为奇数，b为偶数时，gcd(a,b) = gcd(a,b／２) = gcd(a ，ｂ>>１)。

当a和b均为奇数时，先利用更相减损法运算一次，gcd(a,b) = gcd(ａ－ｂ,b)，此时ａ－ｂ必然是偶数，接而继续进行移位运算。

• 优点：不但避免了取模运算，而且算法性能稳定
• 缺点：代码比较复杂

 //更相减损法（位运算优化）
    public static int getGreatestCommonDivisor4(int a, int b) {
        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {// a,b都是偶数
            return getGreatestCommonDivisor4(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {// a为偶数，b为奇数
            return getGreatestCommonDivisor4(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {// a为奇数，b为偶数
            return getGreatestCommonDivisor4(a, b >> 1);
        } else {// a,b都是奇数
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return getGreatestCommonDivisor4(big - small, small);
        }
    }

5. 时间复杂度

• 暴力枚举法：O(min(a,b))
• 辗转相除法：近似于O（log(max(a,b))）
• 更相减损法: O(max(a,b))
• 结合辗转相除法和更相减损法（位运算优化）：O（log(max(a,b))）

6. 完整代码

package gcd;

public class GreatestCommonDivisor {
    public static void main(String[] args) {
        System.out.println(getGreatestCommonDivisor(75, 180));
        System.out.println(getGreatestCommonDivisor2(75, 180));
        System.out.println(getGreatestCommonDivisor3(75, 180));
        System.out.println(getGreatestCommonDivisor4(75, 180));
    }

    // 暴力枚举法
    public static int getGreatestCommonDivisor(int a,int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        for (int i = small / 2; i > 1; i--) {
            if (big % i == 0 && small % i == 0) {
                return i;
            }
        }
        return 1;
    }

    // 辗转相除法
    public static int getGreatestCommonDivisor2(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor2(big % small, small);
    }

    // 更相减损法
    public static int getGreatestCommonDivisor3(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor2(big - small, small);
    }

    //更相减损法（位运算优化）
    public static int getGreatestCommonDivisor4(int a, int b) {
        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {// a,b都是偶数
            return getGreatestCommonDivisor4(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {// a为偶数，b为奇数
            return getGreatestCommonDivisor4(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {// a为奇数，b为偶数
            return getGreatestCommonDivisor4(a, b >> 1);
        } else {// a,b都是奇数
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return getGreatestCommonDivisor4(big - small, small);
        }
    }
}

参考《漫画算法-小灰的算法之旅》