Tìm bội chung nhỏ nhất (LCM) của hai số

Giới thiệu

Trong toán học, Bội chung nhỏ nhất (LCM - Least Common Multiple) là số nguyên dương nhỏ nhất chia hết cho cả hai số.

LCM có thể tính bằng nhiều phương pháp, như phân tích thừa số, v.v. Nhưng trong thuật toán này, ta nhân số lớn hơn với 1, 2, 3... n cho đến khi tìm được một số chia hết cho số thứ hai.

Đầu vào và Đầu ra

Đầu vào: Hai số: 6 và 9
Đầu ra: LCM là: 18

Thuật toán

LCMofTwo(a, b)
Đầu vào: Hai số a và b, coi a > b.
Đầu ra: LCM của a và b.

Begin
    lcm := a
    i := 2
    while lcm mod b ≠ 0, do
        lcm := a * i
        i := i + 1
    done
    return lcm
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int findLCM(int a, int b) {
    // giả sử a lớn hơn b
    int lcm = a, i = 2;
    while(lcm % b != 0) {
        // thử tìm số là bội của b
        lcm = a*i;
        i++;
    }
    return lcm;  // LCM của a và b
}

int lcmOfTwo(int a, int b) {
    int lcm;
    if(a > b)  // để gửi tham số đầu tiên lớn hơn tham số thứ hai
        lcm = findLCM(a,b);
    else
        lcm = findLCM(b,a);
    return lcm;
}

int main() {
    int a, b;
    cout << "Enter Two numbers to find LCM: "; cin >> a >> b;
    cout << "The LCM is: " << lcmOfTwo(a,b);
}

Kết quả

Enter Two numbers to find LCM: 6 9
The LCM is: 18