GCD与LCM

Freak 发布于 2025-03-20 11 次阅读

AI 摘要

在数字的世界里，最大公约数（GCD）与最小公倍数（LCM）揭示了整数之间看似简单却深邃的关系。GCD是那些能共同整除的数中最大的，而LCM则是最小的共享倍数。了解这两个概念不仅是数学基础，也为复杂计算奠定了基础。通过经典的辗转相除法，甚至可以在编程中轻松实现其计算，让我们一起探索这一数学奥秘的魅力吧！

1. 最大公约数（GCD）

1.1 定义

最大公约数（Greatest Common Divisor, GCD）是指能够同时整除两个或多个整数的最大整数。例如，GCD(8, 12) = 4，因为 4 是 8 和 12 的最大公约数。

1.2 性质

  • GCD 是一个非负整数。
  • GCD(a, 0) = |a|，对于任意整数 a。
  • GCD(a, b) = GCD(b, a)，即 GCD 是对称的。
  • 如果 a 是 b 的倍数，则 GCD(a, b) = |b|。

1.3 计算方法

辗转相除法（欧几里得算法）：这是计算 GCD 的经典方法。

  • 公式：GCD(a, b) = GCD(b, a % b)
  • 终止条件：当 b = 0 时，GCD(a, b) = |a|。

1.4 C++实现

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

2. 最小公倍数（LCM）

2.1 定义

最小公倍数（Least Common Multiple, LCM）是指能够被两个或多个整数整除的最小整数。例如，LCM(4, 5) = 20，因为 20 是 4 和 5 的最小公倍数。

2.2 性质

  • LCM 是一个非负整数。
  • LCM(a, 0) = 0，对于任意整数 a（如果包含零）。
  • LCM(a, b) = LCM(b, a)，即 LCM 是对称的。
  • 通过 GCD 可以计算 LCM：GCD(a,b)×LCM(a,b)=∣a×b∣

2.3 计算方法

  • 通过 GCD 计算：利用前面提到的 GCD 计算 LCM。
  • 列举法：列出所有倍数，找到最小的共同倍数，但效率较低。

2.4 C++实现

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