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 // C17 及以上 using namespace std; int main() { int a 56, b 98; cout gcd( a , b ) gcd(a, b) endl; // C17 std::gcd cout lcm( a , b ) lcm(a, b) endl; // C17 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 (C17) using namespace std; // 自定义 gcd 函数兼容 C17 以下 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; // 方法2C17 标准库如果支持 #if __cplusplus 201703L cout \n【C17 标准库】 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来避免整数溢出。C17 及以上版本可以直接使用numeric头文件中的std::gcd和std::lcm。对于 C 语言或旧版 C需要自己实现相关函数。