✨最大公约数
📗简介：
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
📙举个例子：
- 问题：求取21和15的最大公因数
- 方法：辗转相除法（主要介绍）
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
- 具体过程
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数
以问题的15与21为例。
21/15=1 余6
15/ 6=2 余3
6 / 3=2 余0
此时，我们就说3是21与15的最大公约数。
转换为代码看看吧
#include <stdio.h> int gcd(int x,int y) { int t; //辗转相除法的具体体现 while(y) { t=x%y; x=y; y=t; } return x; }
最大公约数得到了，它与最小公倍数又什么联系呢？我们接着向下学习吧。
✨最小公倍数
📗简介：
最小公倍数（Least Common Multiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个自然数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。
用一张图来解释吧！
相信大家已经发现了等量关系：
最小公倍数 * 最大公约数=两个非负整数的乘积
所以我们在求出最大公约数的条件下，最小公倍数格外简单。
int LCM(int x, int y) { return x * y / gcd(x, y); }
好了，每日一数就完成了，嘻嘻。
美图献上：
“总有人间一两风，填我十万八千梦。”
