欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。

算法依赖于定理:

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数.

代码很简单,思想最重要.

public int gcd(int a, int b){       if(a==0){return b;}       return gcd(b % a, a); } 

 欧几里得扩展算法等后续吧....

通俗易懂----欧几里得算法