求最大公约数

1. 暴力枚举法

public class test {

    public static int genGreatestCommonDivisor(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(small %i==0 && big%i==0){
                return i;
            }
        }
        return  1;
    }


    public static void main(String[] args) {
        System.out.println(genGreatestCommonDivisor(25,5));
    }
}

2. 欧几里得算法

public class test {

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


    public static void main(String[] args) {
        System.out.println(genGreatestCommonDivisor(25,10));
    }
}

3. 更相减损术

public class test {

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

       return genGreatestCommonDivisor(big - small,small);
    }


    public static void main(String[] args) {
        System.out.println(genGreatestCommonDivisor(57,10));
    }
}