求最大公约数(gcd)与最小公倍数(lcm)【C/C++】

1. 引言

最大公约数（Greatest Common Divisor，简称 gcd）和最小公倍数（Least Common Multiple，简称 lcm）是数学和计算机科学中两个基础且重要的概念。它们在算法设计、密码学、分数简化、周期计算等众多领域都有广泛应用。本文将详细介绍 gcd 和 lcm 的定义、计算方法，并重点提供 C 和 C++ 语言下的多种实现方案。

2. 基本概念

2.1 最大公约数 (gcd)

对于两个整数 a 和 b，它们的最大公约数是指能够同时整除 a 和 b 的最大正整数。记为 gcd(a, b)。

示例：gcd(12, 18) = 6，因为 6 是能同时整除 12 和 18 的最大整数。

2.2 最小公倍数 (lcm)

对于两个整数 a 和 b，它们的最小公倍数是指能够同时被 a 和 b 整除的最小正整数。记为 lcm(a, b)。

示例：lcm(4, 6) = 12，因为 12 是能被 4 和 6 整除的最小正整数。

2.3 gcd 与 lcm 的关系

对于任意两个正整数 a 和 b，存在以下重要关系：

lcm(a, b) = a * b / gcd(a, b)

因此，在计算出 gcd 后，可以非常高效地求出 lcm。

3. 计算方法与 C/C++ 实现

3.1 辗转相除法（欧几里得算法）

这是计算 gcd 最经典、最高效的算法。其原理基于：gcd(a, b) = gcd(b, a % b)，直到余数为 0，此时的除数即为最大公约数。

C 语言实现（递归版本）：

#include <stdio.h> int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { int a = 56, b = 98; printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b)); return 0; }

C++ 语言实现（迭代版本）：

#include <iostream> using namespace std; int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } int main() { int a = 56, b = 98; cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl; return 0; }

3.2 更相减损术

另一种方法，原理是：gcd(a, b) = gcd(a - b, b)（假设 a > b），直到两数相等，该数即为最大公约数。效率通常低于辗转相除法，但易于理解。

C++ 实现：

int gcd_subtraction(int a, int b) { while (a != b) { if (a > b) a = a - b; else b = b - a; } return a; }

3.3 使用 C++ 标准库

C++ 17 及以后的标准库<numeric>头文件中提供了std::gcd和std::lcm函数，可以直接使用。

#include <iostream> #include <numeric> // C++17 及以上 using namespace std; int main() { int a = 56, b = 98; cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl; // C++17 std::gcd cout << "lcm(" << a << ", " << b << ") = " << lcm(a, b) << endl; // C++17 std::lcm return 0; }

3.4 计算最小公倍数 (lcm)

基于关系式lcm(a, b) = a * b / gcd(a, b)实现。需要注意整数溢出问题，可以先除后乘：a / gcd(a, b) * b。

C 语言实现：

#include <stdio.h> int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } long long lcm(int a, int b) { // 先除后乘，避免溢出 return (long long)a / gcd(a, b) * b; } int main() { int a = 12, b = 18; printf("lcm(%d, %d) = %lld\n", a, b, lcm(a, b)); return 0; }

4. 完整示例程序

下面是一个完整的 C++ 程序，包含用户输入、计算并输出结果。

#include <iostream> #include <numeric> // 用于 std::gcd (C++17) using namespace std; // 自定义 gcd 函数（兼容 C++17 以下） int my_gcd(int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; } // 自定义 lcm 函数 long long my_lcm(int a, int b) { return (long long)a / my_gcd(a, b) * b; } int main() { int a, b; cout << "请输入两个正整数（以空格分隔）: "; cin >> a >> b; if (a <= 0 || b <= 0) { cout << "输入必须为正整数！" << endl; return 1; } // 方法1：自定义函数 int gcd1 = my_gcd(a, b); long long lcm1 = my_lcm(a, b); cout << "【自定义函数】" << endl; cout << "gcd(" << a << ", " << b << ") = " << gcd1 << endl; cout << "lcm(" << a << ", " << b << ") = " << lcm1 << endl; // 方法2：C++17 标准库（如果支持） #if __cplusplus >= 201703L cout << "\n【C++17 标准库】" << endl; cout << "std::gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl; cout << "std::lcm(" << a << ", " << b << ") = " << lcm(a, b) << endl; #endif return 0; }

5. 总结

• 最大公约数 (gcd)和最小公倍数 (lcm)是基础数学工具，在编程中频繁使用。
• 辗转相除法（欧几里得算法）是计算 gcd 最高效、最常用的方法。
• gcd 和 lcm 满足关系：lcm(a, b) = a * b / gcd(a, b)。
• 计算 lcm 时，建议使用a / gcd(a, b) * b来避免整数溢出。
• C++17 及以上版本可以直接使用<numeric>头文件中的std::gcd和std::lcm。
• 对于 C 语言或旧版 C++，需要自己实现相关函数。