首页C语言求两个数的最大公因数和最小公倍数

C语言求两个数的最大公因数和最小公倍数

时间: 2025-06-21 21:29:54 浏览: 3

### C语言实现求解两个数的最大公因数和最小公倍数为了计算两个整数的最大公因数 (GCD) 和最小公倍数 (LCM)，可以采用更高效的算法而不是简单的线性查找。这里介绍一种基于欧几里得算法的方法来求最大公因数，并通过两数乘积除以最大公因数的方式获得最小公倍数。 #### 使用辗转相除法（欧几里得算法）这种方法不仅效率高而且易于理解。以下是完整的C语言代码示例： ```c #include <stdio.h> // 函数用于交换两个变量的值 void swap(long long *a, long long *b) { long long temp = *a; *a = *b; *b = temp; } int main() { long long n, m; // 输入两个正整数 printf("请输入两个正整数: "); scanf("%lld %lld", &n, &m); // 如果第一个数小于第二个数，则交换它们的位置以便后续处理 if (n < m) { swap(&n, &m); } // 辗转相除法求最大公约数 while(m != 0){ long long remainder = n % m; n = m; m = remainder; } // 输出最大公因数 printf("这两个数的最大公因数为：%lld\n", n); // 计算并输出最小公倍数 // 需要注意的是，在实际应用中应该考虑溢出风险，此处假设输入数据不会引起溢出 long long original_n, original_m; original_n = n; // 存储原始的第一个数值 original_m = m; // 此处实际上已经是最后余数即最大公因数 // 恢复原来的较大值给'n' n = original_n / n * original_m; printf("这两个数的最小公倍数为：%lld\n", n); return 0; } ``` 上述代码实现了以下功能： - 用户可以从控制台输入一对正整数。 - 利用辗转相除法高效地找出这对数字之间的最大公因数[^3]。 - 基于已知的最大公因数快速得出最小公倍数[^3]。

阅读全文