Bài toán

Đề bài: Nhập vào hai số nguyên dương a , b . Tính ước số chung lớn nhất và bội số chung nhỏ nhất của a, b.

Hướng dẫn giải

Trước khi đi vào giải bài toán thì chúng ta có thể hiểu qua về hai định nghĩa ước chung lớn nhất và bội chung nhỏ nhất.

Ước chung lớn nhất của hai số nguyên dương a, b là một số nguyên dương lớn nhất là ước chung của hai số a và b.

Bội chung nhỏ nhất của hai số nguyên dương a, b là một số nguyên dương nhỏ nhất mà có thể chia hết cho a và b.

Cách tính ước chung lớn nhất

B1: So sánh a, b. Nếu a == b thì chúng ta có thể kết luận ước chung lớn nhất là a.

B2: So sánh a, b.

  • Nếu a > b thì chúng ta gán a = a - b. Tiếp theo chúng ta quay lại B1.

  • Nếu a < b thì chúng ta gán b = b - a. Tiếp theo chúng ta quay lại B1.

Cách tính bội chung nhỏ nhất

Chúng ta sẽ tính bội chung nhỏ nhất theo công thức sau:

BCNN = a * b / UCLN(a, b)

Code

Dưới đây là source code bạn có thể tham khảo

#include <stdio.h>

int gcd(int a, int b)
{
  if (a == b) return a;
  if (a < b) return gcd(a, b - a);
  return gcd(a - b, b);
}

int lcd(int a, int b)
{
  return a * b / gcd(a, b);
}

int main()
{
  int a, b;

  printf("a: ");
  scanf("%d", &a);
  printf("b: ");
  scanf("%d", &b);

  printf("Greatest Common Divisor: %d\n", gcd(a, b));
  printf("Least Common Multiple: %d\n", lcd(a, b));
}