在 C 中查找两个 nos 的 LCM

Question

我创建了一个代码来查找两个nos的LCM。我认为代码是正确的，但我有一个不需要的输出。这段代码有什么问题？

#include<stdio.h>
#include<conio.h>
main()
{
int i, j, a, b, lcm;
printf("Enter two nos : ");
scanf("%d %d", &a, &b);
for(i=1; i<=b; i++)
{
for(j=1; j<=a; j++)
{
if(a*i==b*j)
{
lcm=a*i;
break;
}
}
}
printf("LCM=%d", lcm);
getch();
}

Answer 1

两个数字 a，b 的 LCM 至少是 max(a，b( 和最多 a*b，所以你对边界的第一个想法是正确的。但是，如果您仔细查看LCM(两个正整数(a和b的定义之一，您会发现LCM是最小的数字，因此LCM % a = 0和LCM % b = 0，其中"%"表示"整数除法的余数，截断"，这正是您可以在此处使用的。

例：

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a, b, lcm;
printf("Enter two nos : ");
scanf("%d %d", &a, &b);
/* TODO: checks and balances! */
/* Set lcm to the larger of the two numbers */
lcm = (a < b) ? b : a;
/* check if both "a" and "b" divide "lcm" without a remainder
* otherwise increment "lcm" */
for (;;) {
if ((lcm % a == 0) && (lcm % b == 0)) {
/* we got the LCM, break out of loop */
break;
}
/* Otherwise increment "lcm" by one */
lcm++;
}
printf("LCM = %dn", lcm);
exit(EXIT_SUCCESS);
}

有更优雅和更通用的方法，但我认为上面的例子很容易遵循。