gcd和lcm(最大公约数，最小公倍数)

gcd（greatest common divisor）为最大公约数，lcm（least common multiple）为最小公倍数。
**

gcd算法

**
gcd算法，运用的是欧几里得算法，也就是辗转相除法，具体原理是：
1.有两个数a和b，我们把较大的数传给maxn,较小的数传给minx
2.用maxn对minx进行取余运算，如果余数为0，那么a,b的最大公约数为a,
3.若余数不为0，a,b的最大公约数为minx和余数的最大公约数，我们在循环到第一步进行计算
代码展示

int gcd (int a,int b) { //b为较大的那个数，即maxn
	while(b%a != 0&&a) {
		int ans  = b%a;
		b = a;
		a = ans;
	}
	return a ;
}

**

lcm算法

**
求两个数的最小公倍数，我们利用gcd算法求出两数最大公约数，两个数相乘然后除最大公约数即为最小公倍数，代码如下：

int lcm (int a,int b) {
	return a*b/gcd(a,b);
}

拓展：gcd求最大公约数不仅可以用辗转相除法，还可以用更相减损术，暴力枚举，
更相减损术原理：两个正整数a和b(a>b)，它们的最大公约数等于 a-b 的减值c和较小数b的最大公约数。

//更相减损术
int gcd(int a,int b) {
	while (a != b) {
    	if (a > b) 
      		a -= b;
      	else 
      		b -= a;
  	}
  return a;
}

比较：
暴力枚举时间复杂度：O(min(a,b));
辗转相除法时间复杂度：O(log(max(a,b)))
更相减损术时间复杂度：O(max(a,b))
相比之下辗转相除法更稳定于O(log(N)),从一般角度看，两者本质上没有区别，但是当遇到两个数相差较大时，我们就需要用更多的减法才可以来完成操作，但是很明显，除法更加快捷。
但辗转相除法的取模运算性能较差
所以在实际的编码过程中还是靠自己判断要用哪种方式，但是一般情况下辗转相除法可以满足大部分的题目