时间戳

首页 > 解决方案 > 在 C 中找到两个没有的 LCM

c - 在 C 中找到两个没有的 LCM

问题描述

我创建了一个代码来查找两个没有的 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();
}

标签： clcm

解决方案

两个数字 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);
}

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

推荐阅读