首页求两个自然数m和n的最大公约数和最小公倍数。输入描述：输入一行数据：m和n的数值。输出描述：最大公约数和最小公倍数。用c语言 1.设计3个以上求两个自然数的最大公约数和最小公倍数的算法

求两个自然数m和n的最大公约数和最小公倍数。输入描述：输入一行数据：m和n的数值。输出描述：最大公约数和最小公倍数。用c语言 1.设计3个以上求两个自然数的最大公约数和最小公倍数的算法

时间: 2025-02-16 08:14:45 浏览: 39

在C语言中，求两个自然数m和n的最大公约数（GCD, Greatest Common Divisor）和最小公倍数（LCM, Least Common Multiple）通常可以使用欧几里得算法（辗转相除法）和它们的关系来实现： 1. **欧几里得算法** (Euclidean Algorithm): - 定义两个整数a和b（假设a >= b），它们的最大公约数是b和a%b的最大公约数。 - 当b等于0时，a就是最大公约数。 ```c int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } ``` 2. **计算最小公倍数** (LCM): - 最小公倍数可以通过公式 `(a * b) / gcd(a, b)` 来计算，因为gcd(a, b)始终能整除a和b，所以这个乘积一定是它们的倍数。 ```c int lcm(int m, int n) { return (m * n) / gcd(m, n); } ``` 完整程序示例： ```c #include <stdio.h> // 用于计算最大公约数的函数 int gcd(int a, int b); int main() { int m, n; printf("请输入两个自然数m和n："); scanf("%d %d", &m, &n); // 计算并打印最大公约数和最小公倍数 int gcd_value = gcd(m, n); int lcm_value = lcm(m, n); printf("最大公约数 (GCD): %d\n", gcd_value); printf("最小公倍数 (LCM): %d\n", lcm_value); return 0; } // 辅助函数，欧几里得算法求最大公约数 int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } ```

阅读全文