用户输入的N个数的最大公约数和最小公约数

Question

我需要编写一个c程序，其中N个不同的正数将从用户取为一个包含N个元素的整数a数组。假设输入的数字为正数，如果未输入数字，则不会进行检查。所有这些整数的最大公约数和最小公约数将被计算并写入屏幕。示例：对于N=4，从用户接收的值应存储在A数组中，作为A=[10，50，15，30]。因此以下输出应写在屏幕上。GCD(10，50，15，30(=5，LCM(10，50,15,30(=150

我可以计算两个数字的gcd和lcd问题是如何对n个整数执行此操作。我应该使用哪种算法<另一个问题是我不能定义函数，不能使用break-and-continue命令>

这是我的2个整数的代码

#include <stdio.h>
int main()
{
int n1, n2;

printf("enter 2 integers: ");
scanf("%d %d",&n1,&n2);
while(n1!=n2)
{
if(n1 > n2)
n1 -= n2;
else
n2 -= n1;
}
printf("gcd = %d",n1);
return 0;
}

Answer 1

要计算2个正整数的GCD，可以使用欧几里得算法。要计算LCM，只需注意lcm(a,b) = a * b / gcd(a,b)

现在，如果你需要计算N个数字的GCD和LCM，请意识到gcd(a,b,c) = gcd(gcd(a,b), c)和类似的lcm(a,b,c) = lcm(lcm(a,b),c)。你应该能够开发一个迭代算法来找到你想要的答案。

下面是我执行您描述的任务的代码。

#include <stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int main(void) {
int n;
scanf("%d", &n);
int g = 0, m = 1, x;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
g = gcd(g, x);
m = lcm(m, x);
}
printf("gcd = %dn", g);
printf("lcm = %dn", m);
return 0;
}