最大公约数

数学原理

求最大公约数需要用到辗转相除法（又名欧几里得算法）。例如24和15.
计算过程：
$$24\div15=1...9$$
$$15\div9=1...6$$
$$9\div6=1...3$$
$$6\div3=1...0$$
至此，运算结束。简单的理解就是拿数字a去除以数字b，得到商和余数，然后再拿运算的除数去除以余数。重复这个过程，当余数为0时。这个除数就是我们要求的最大公约数。
我们只需要知道大概怎么用就可以。如果对原理感兴趣可以自行查询。

代码实现

python代码

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


print(gcd(15, 24))
print(gcd(24, 18))

每次进行运算的都是两个数，我们甚至不需要定义第三个变量。直接a变成除数b（a=b）。让b变成a和b的余数（b=a%b）。就是我们上面的过程。然后在while循环里执行。当b也就是余数为0的时候循环结束。这个时候的除数a就是我们要求的结果了。

c++代码

#include<iostream>
using namespace std;
int gcd(int a, int b)
{
    int temp;
    while (b)
    {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}
int main()
{
    cout << gcd(24, 15) << endl << gcd(30, 18) << endl;
}

c++里面没有元组赋值的写法，所以我们要先用一个变量把a存起来。a=b执行之后。a的值已经改变了，那么b=a%b的值肯定就不正确了。

最小公倍数

我们会求最大公约数，那么最小公倍数就很简单了，只需要记住一个公式就可以：
$$LCM(a,b)=\frac{|a\times b|}{GCD(a,b)}$$
直接把值往公式里面代入即可

c++代码

#include<iostream>
using namespace std;
#include<cmath>
int gcd(int a, int b)
{
    int temp;
    while (b)
    {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}
int lcm(int a, int  b)
{
    return abs(a * b) / gcd(a, b);
}
int main()
{
    cout << gcd(24, 15) << endl << gcd(30, 18) << endl;
    cout << lcm(24, 15) << endl << lcm(30, 18) << endl;
}

python代码

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return abs(a * b) // gcd(a, b)


print(gcd(15, 24))
print(gcd(24, 18))
print(lcm(15, 24))
print(lcm(24, 18))