欧几里得算法：计算两个非负整数p和q的最大公约数：若q是0，则最大公约数是p；不然，将p除以q获得余数r，p和q的最大公约数即为q和r的最大公约数。算法
递归spa
1 int gcd_recursion(int p, int q){ 2 //p >= q 3 if( q == 0 ) 4 return p; 5 6 int r = p%q; 7 return gcd_recursion( q, r); 8 }
迭代code
int gcd_itera(int p, int q){ if( p < q ){ int tmp = p; p = q; q = tmp; } if( q == 0 ) return p; while( p > 0 ){ int r = p%q; p = q; q = r; if( r == 0 ) break; } return p; }
最小公倍数 = 数1 * 数2 * gcd(数1， 数2)blog
1 int mcm(int p, int q){ 2 return p*q*gcd_itera(p, q); 3 }