c - 求C中两个数的LCM

Question

我创建了一个代码来查找两个编号的 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 = %d\n", lcm);

  exit(EXIT_SUCCESS);
}

还有更优雅、更通用的方法，但我认为上面的例子很容易理解。