求两数最大公约数（java）_求两个数的最大公约数java

1、辗转相除法
辗转相除法：以大数除以小数，如果能整除，那么小数就是所求的最大公约数。否则就用除数来除以余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。
如两个整数a>b；a/b=商 余数c， a和b的最大公约数 就是 b和c的最大公约数

例如：求 4453 和 5767 的最大公约数时，可作如下除法．
5767÷4453＝1 余 1314
4453÷1314＝3 余 511
1314÷511 ＝2 余 292
511 ÷292 ＝1 余 219
292 ÷219 ＝1 余 73
219÷73＝3 于是得知，5767 和 4453 的最大公约数是 73。辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数。

当两数很大时取模运算的性能差，引出下一个方法。

2、更相减损术：

它也相当不稳定，当计算10000 和 1时要递归9999次

3、位移 结合 更相减损法（最优）

3种方法的代码

package jzOffer.simple;

//最大公约数
public class GreatestCommonDisvisor {
    //1、辗转相除法
    public static int getGreatestCommonDisvisor1(int a,int b){
        if (a==b)return a;
        int big = a>b?a:b;
        int small = a<b?a:b;
        if (big%small==0) return small;
        return getGreatestCommonDisvisor1(small,big%small);
    }
    //2、更相减损法
    public static int getGreatestCommonDisvisor2(int a,int b){
        if (a==b)return a;
        int big = a>b?a:b;
        int small = a<b?a:b;
        return getGreatestCommonDisvisor1(small,big-small);
    }

    //3、位移 结合 更相减损法（最优）
    public static int gcd(int a,int b){
        if (a==b)return a;
        //a&1 如果a是偶数，那么二进制的最后一位一定是0，如果a是奇数，那么二进制的最后一位一定是1
        if((a&1)==0 && (b&1)==0){//如果都为偶数，两数除以2
            return gcd(a>>1,b>>1);
        }else if((a&1)==0 && (b&1)!=0){//如果a为偶数，b为奇数
            return gcd(a>>1,b);
        }else if((a&1)!=0 && (b&1)==0){//如果a为奇数偶数，b为偶数
            return gcd(a,b>>1);
        }else {//两数都为奇数 更相减损法(减完就是偶数了)
            int big = a>b?a:b;
            int small = a<b?a:b;
            return gcd(small,big-small);
        }

    }

    public static void main(String[] args) {
        int i=getGreatestCommonDisvisor1(100,9);
        System.out.println(i);
        int j=getGreatestCommonDisvisor2(100,5);
        System.out.println(j);
        int k=gcd(100,9);
        System.out.println(k);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48