Chương trình C++ tìm Bội chung nhỏ nhất (LCM)

Bội chung nhỏ nhất (LCM) của hai số là số nhỏ nhất là bội của cả hai số đó.

Ví dụ: Giả sử chúng ta có hai số: 15 và 9.

15 = 5 * 3
9 = 3 * 3

Vậy LCM của 15 và 9 là 45.

Chương trình tìm LCM của hai số được đưa ra như sau:

Ví dụ 1: Dùng vòng lặp

#include <iostream>
using namespace std;

int main() {
    int a = 7, b = 5, lcm;
    if (a > b)
        lcm = a;
    else
        lcm = b;
    while (1) {
        if (lcm % a == 0 && lcm % b == 0) {
            cout << "The LCM of " << a << " and " << b << " is " << lcm;
            break;
        }
        lcm++;
    }
    return 0;
}

Đầu ra

The LCM of 7 and 5 is 35

Trong chương trình trên, biến lcm được đặt là số lớn hơn trong hai số. Điều này được minh họa bằng đoạn mã sau:

if (a > b) lcm = a; else lcm = b;

Sau đó, một vòng lặp while chạy. Trong vòng lặp này, nếu LCM chia hết cho cả a và b, thì đó là LCM của hai số và được hiển thị. Nếu không, LCM được tăng lên cho đến khi điều kiện này được thỏa mãn.

while (1) {
    if (lcm % a == 0 && lcm % b == 0) {
        cout << "The LCM of " << a << " and " << b << " is " << lcm;
        break;
    }
    lcm++;
}

Ví dụ 2: Sử dụng công thức LCM và GCD

Một phương pháp khác để tìm LCM của hai số là sử dụng công thức liên quan đến LCM và GCD. Công thức này quy định rằng tích của hai số bằng tích của LCM và GCD của chúng.

a * b = GCD * LCM

Chương trình tìm LCM bằng công thức:

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a = 7, b = 5;
    cout << "LCM of " << a << " and " << b << " is " << (a * b) / gcd(a, b);
    return 0;
}

Đầu ra

LCM of 7 and 5 is 35

Trong chương trình trên, LCM được tìm bằng công thức. Trước tiên, GCD của a và b được lấy bằng hàm gcd(). Đây là một hàm đệ quy. Nó có hai tham số là a và b. Nếu b bằng 0, thì a được trả về cho hàm main(). Ngược lại, hàm gcd() gọi đệ quy chính nó với các giá trị b và a % b.

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

Sau khi có GCD, LCM được tính bằng công thức và hiển thị:

cout << "LCM of " << a << " and " << b << " is " << (a * b) / gcd(a, b);