欧几里得算法

欧几里得算法（gcd）

重新看了一下简单的gcd算法，有了一些更深的理解方式。

概括的说，gcd算法其实就是连续进行带余除法直到余数为零。

举个例子，求（72，30），

我们知道（a+kb,b)=(a,b)=(b,a)

于是，（72，30）=（30*2+12，30）=（30，12）=（12*2+6，12）=（12，6）=（6*2，6）=（6，0）

我们知道，一个正整数与0的最大公约数为这个正整数本身，于是我们就将（72，30）这个问题转化成了（6，0），gcd为6显而易见。