最大公约数

最大公约数(greatest common divisor)：辗转相除法（ 欧几里得算法）
用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 

  1. // 迭代, a > b, 且b不为0
  2. int gcd(int a, int b)
  3. {
  4.     while(a % b){
  5.         int tmp = a;
  6.         a = b;
  7.         b = tmp % b;
  8.     }
  9.     return b; 
  10. }
  11. // 递归写法
  12. int gcd(int a, int b) 
  13. { 
  14.     // return b == 0 ? a : gcd(b, a % b); // a, b可以为0
  15.     return a % b == 0 ? b : gcd(b, a % b); // b不能为0 
  16. }
  17. // 函数
  18. __gcd(a, b);

最小公倍数

最小公倍数 = 两数之积除以最大公约数

  1. #include<algorithm>
  2. /* C++ 最小公倍数 = 两数之积除以最大公约数 */
  3. return (a * b) / __gcd(a, b);