C语言——最大公因数和最小公倍数

在计算机科学中，求解两个或多个数的最大公因数（Greatest Common Divisor，简称GCD）和最小公倍数（Least Common Multiple，简称LCM）是数学计算中的基本问题。C语言作为一种广泛应用于科学计算和工程领域的编程语言，自然也可以用来求解这些问题。本文将详细介绍C语言中求最大公因数和最小公倍数的方法，并附上代码示例。

一、最大公因数

求最大公因数的方法有很多，其中较著名的有欧几里得算法（Euclidean Algorithm）和辗转相除法（Division Algorithm）。在这里，我们以欧几里得算法为例进行讲解。

欧几里得算法的基本思想是：两个数的最大公因数等于较大数与较小数的最大公因数。具体步骤如下：

初始化一个循环，令较大数为a，较小数为b；
在循环中，用较大数除以较小数，得到余数；
将较大数更新为较小数，将余数更新为较大数；
重复步骤2和3，直到较小数为0；
最大公因数即为初始的较大数。

示例代码：

#include <stdio.h>int gcd(int a, int b) {while (b != 0) {int temp = a;a = b;b = temp % b;}return a;
}int main() {int a, b;printf("请输入两个整数：");scanf("%d %d", &a, &b);int result = gcd(a, b);printf("最大公因数是：%d\n", result);return 0;
}

运行结果：

在这里插入图片描述

二、最小公倍数

求最小公倍数的方法有很多，其中较著名的方法是：两个数的最小公倍数等于它们的乘积除以最大公因数。具体计算公式如下：

最小公倍数 = (a * b) / 最大公因数

示例代码：

#include <stdio.h>int gcd(int a, int b) {while (b != 0) {int temp = a;a = b;b = temp % b;}return a;
}int lcm(int a, int b) {return (a * b) / gcd(a, b);
}int main() {int a, b;printf("请输入两个整数：");scanf("%d %d", &a, &b);int result = lcm(a, b);printf("最小公倍数是：%d\n", result);return 0;
}