最大公约数

求一个数的最大公约数，getGreatestCommonDivisor简称gcd

辗转相除法

又名 欧几里得算法

原理

两个正整数a，b（a>b），它们的最大公约数等于 a/b的余数 和 b 之间的最大公约数

实现

public static int gcd(int a, int b){
    int big = a>b? a:b;
    int small = a<b? a:b;
    if(big%small == 0)
        return small;
    
    return gcd(big%small, small);
}

缺点

两个整数较大时，模运算性能较差

更相减损术

原理

两个正整数a，b（a>b），它们的最大公约数等于 a-b的差值 和 较小数b的最大公约数

实现

public static int gcd(int a, int b){
    if(a == b)
        return a;
    
    int big = a>b? a:b;
    int small = a<b? a:b;

    return gcd(big-small, small);
}

缺点

不稳定，当两个数悬殊巨大时，要计算多次，例如：100001和1

移位运算法

这个算法结合了 辗转相除法 和 *更相减损术 的优势，在更相减损术的基础上使用移位运算，整个算法只用到 移位运算 和 减法

• 这个算法在两个数比较小时看不出优势，但是当数比较大的时候，计算速度明显提高

原理

两个正整数a，b（a>b）

1. gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
2. gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
3. 当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数和一个奇数的最大公约数时，可以先将偶数除以2。

实现

public static int gcdPlus(int a, int b){
    if(a == b)
        return a;
    
    //采用与1进行与的位运算判断奇偶数，速度更快
    if((a&1)==0 && (b&1) ==0)//a，b均为偶数
        return gcdPlus(a>>1, b>>1)<<1;
    else if((a&1)==0 && (b&1) !=0)//a为偶数，b为奇数
        return gcdPlus(a>>1, b);
    else if((a&1)==0 && (b&1) !=0)//a为奇数，b为偶数
        return gcdPlus(a, b>>1);
    else{
        int big = a>b? a:b;
        int small = a<b? a:b;
        return gcdPlus(big-small, small);
    }
}

时间复杂度

1. 暴力法：O(min(a, b))
2. 辗转相除法：近似为O(log(max(a, b)))，但是模运算性能较差
3. 更相减损术：算法不稳定，最坏为O(max(a, b))
4. 移位运算法：不但避免模运算，而且稳定，复杂度为O(log(max(a, b)))