c语言最大公约数和最小公倍数的求法

在C语言中，求两个整数的最大公约数（GCD）和最小公倍数（LCM）是常见的编程任务。以下是常用的方法及实现示例：

一、最大公约数（GCD）的求法

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

这是最常用且高效的方法，通过反复取余实现。 递归公式：`gcd（a, b） = gcd（b, a % b）`

当余数为0时，另一个数即为GCD。

更相减损术

通过不断相减求余数，直到两数相等。 适用于较小数值的计算。

二、最小公倍数（LCM）的求法

LCM可以通过GCD计算：

`lcm（a, b） = |a * b| / gcd（a, b）`

需要注意处理负数情况，取绝对值。

三、代码实现示例

```c

include

include

// 辗转相除法求GCD

int gcd(int a, int b) {

while (b != 0) {

int temp = b;

b = a % b;

a = temp;

}

return a;

}

// 计算LCM

int lcm(int a, int b) {

return (a * b) / gcd(a, b);

}

int main() {

int n, i, a[N];

printf("请输入整数个数（≥2）：");

scanf("%d", &n);

if (n < 2) {

printf("至少需要输入2个数

");

return 1;

}

printf("请输入 %d 个整数：\n", n);

for (i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

// 计算并输出GCD

printf("最大公约数：\n");

for (i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

int current_gcd = gcd(a[i], a[j]);

printf("%d 和 %d 的最大公约数是：%d

", a[i], a[j], current_gcd);

}

}

// 计算并输出LCM

printf("最小公倍数：\n");

for (i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

int current_lcm = lcm(a[i], a[j]);

printf("%d 和 %d 的最小公倍数是：%d

", a[i], a[j], current_lcm);

}

}

return 0;

}

```

四、代码说明

函数`gcd`：

使用辗转相除法递归计算两个数的最大公约数。

函数`lcm`：

通过公式计算最小公倍数，并处理负数情况。

主函数`main`

- 读取用户输入的整数个数及具体数值。

- 使用双重循环计算每对数的GCD和LCM，并输出结果。

五、注意事项

输入时建议使用`%d`格式说明符读取整数，注意检查输入有效性。

对于多个数，采用两两计算的方式效率较高，时间复杂度为O（n² log（min（a_i）））。

通过上述方法，可以高效地实现C语言中最大公约数和最小公倍数的计算。