C++欧几里得算法求最大公约数和最小公倍数
阅读原文时间:2023年08月12日阅读:2

定义

最大公约数即为 Greatest Common Divisor,常缩写为 gcd。

一组整数的公约数,是指同时是这组数中每一个数的约数的数。

一组整数的最大公约数,是指所有公约数里面最大的一个。

那么如何求最大公约数呢?我们先考虑两个数的情况。

欧几里得算法

如果我们已知两个数 \(a\) 和 \(b\),如何求出二者的最大公约数呢?

不妨设\(a > b\)

我们发现如果 b 是 a 的约数,那么 b 就是二者的最大公约数。 下面讨论不能整除的情况,即\(a = b * q + r\),

其中\(r < b\)

我们通过证明可以得到\(gcd(a, b) = gcd(b, amodb)\),过程如下:

设 \(a=bk+c\),显然有 \(c=a \bmod b\)。设 \(d \mid a\),\(~d \mid b\),则\(c=a-bk\), \(\frac{c}{d}=\frac{a}{d}-\frac{b}{d}k\)。

由右边的式子可知\(\frac{c}{d}\) 为整数,即 \(d \mid c\),所以对于 \(a\),\(b\) 的公约数,它也会是 \(b\),\(a \bmod b\) 的公约数。

反过来也需要证明:

设 \(d \mid b\),\(~d\mid (a \bmod b)\),我们还是可以像之前一样得到以下式子

\(\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,~\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}\)。

因为左边式子显然为整数,所以\(\frac{a}{d}\) 也为整数,即 d \mid a,所以 b,a\bmod b 的公约数也是 a,b 的公约数。

既然两式公约数都是相同的,那么最大公约数也会相同。

所以得到式子\(gcd(a, b) = gcd(b, amodb)\)

既然得到了 \(\gcd(a, b) = \gcd(b, r)\),这里两个数的大小是不会增大的,那么我们也就得到了关于两个数的最大公约数的一个递归求法。

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

最小公倍数

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}
int lcm = a * b / gcd(a, b);

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章