题解 | #最大公约数#更相减损法

这个思想起源于我国古代的《九章算术》，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。原文是这么描述的：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成白话将就是：

第一步：对于任意给定的两个正整数a、b，要求出他们的最大公约数，首先判断他们俩是否都是偶数（能被2整除），如果都是偶数则一直除以2约简，直至不能再被2整除,while(a%2==0 && b%2==0){a = a/2;,b=b/2;}；

第二步：如果不是，那么就执行下一步，即用较大的数减去较小的数，然后将所得的差值赋值给原先拥有较大值的那个变量，再拿这个变量与较小值的那个变量进行比较，继续用二者中较大的减去较小的，直到两个变量相等；

    public int gcd (int a, int b) {
        // write code here
        if (a % b == 0 || b % a == 0){

            return a % b == 0 ? b : a;
        }

        while(a != b){

            if(a > b){
                a = a - b;
            }else{
                b = b - a;
            }
        }

        return a;
    }