每日一数——最大公约数与最小公倍数

✨最大公约数

📗简介：

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

📙举个例子：

• 问题：求取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);
}

好了，每日一数就完成了，嘻嘻。

美图献上：

“总有人间一两风，填我十万八千梦。”