欧几里德算法

有点醉了,序幕给个例子说明算法,求最大公约数,居然不知道最大公约数是什么

比如:12 和 16 最大公约数是4(突然想到因式分解) 最大公倍数 48(还是因式分解) 我想起了什么....

然后看到了欧几里得算法:

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。

什么鬼啊...感觉在学高中数学

把简单的推到过程写下来吧:

假设 a,b两个数 a比b大,d是他们的最大公约数

所以 d|a d|b (即d既能被a整除又能被b整除)

设 a = kb + r

故 r = a - kb

所以 r能被d整除 ,即d|a

故 d是r和b的最大公约数

java实现如下:

    public int gcd(int p, int q) {
        if (0 == q) {
            return p;
        }
        int r = p%q;
        return gcd(q, r);
    }