Bài 25. Tìm bội chung nhỏ nhất của 2 số

Cách tìm bội chung nhỏ nhất của 2 số

Trong lĩnh vực tư duy lập trình, bài tập tìm bội chung nhỏ nhất của 2 số là một bài tập cơ bản giúp các bạn sinh viên rèn luyện tư duy và kỹ năng lập trình. Bài viết này sẽ giới thiệu các phương pháp khác nhau để giải bài tập này. Mỗi phương pháp sẽ có ý tưởng, triển khai và mã code tương ứng.

1. Bội chung nhỏ nhất là gì?

Theo định nghĩa, bội chung nhỏ nhất của hai số nguyên a và b là số nguyên dương nhỏ nhất mà cả a và b đều chia hết cho nó mà không để lại số dư. Trường hợp a hoặc b là 0, thì không tồn tại số nguyên dương chia hết cho cả a và b, khi đó quy ước rằng Bội chung nhỏ nhất của a và b là 0.

2. Các thuật toán tìm bội chung nhỏ nhất của 2 số

Có nhiều thuật toán để tìm bội chung nhỏ nhất của 2 số, sau đây là một số phương pháp phổ biến:

Cách 1: Lặp tăng dần

Phương pháp này khá đơn giản, ta chỉ cần lặp từ nhỏ tới lớn các số trong đoạn từ max(a, b) đến a*b, và tìm số đầu tiên chia hết cho cả a và b.

Đánh giá: Phương pháp này trong trường hợp xấu nhất sẽ cần a*b - max(a, b) lần lặp. Tuy nhiên, có thể tối ưu hơn với phương pháp thứ hai.

#include 
#include 
int main(){
    int a = 5, b = 7, lcm;
    int maxV = a*b;
    for(int i = std::max(a, b); i <= maxV; i++){
        if(i % a == 0 && i % b == 0){
            lcm = i;
            break;
        }
    }
    printf("BCNN(%d, %d) = %d", a, b, lcm);
}

Cách 2: Tối ưu lặp của cách 1

BCNN của 2 số a và b phải chia hết cho cả a và b. Do đó, ta chỉ cần duyệt qua các số chia hết cho một số (hoặc a, hoặc b). Nhưng để tối ưu, hãy duyệt qua các số chia hết cho max(a, b).

Ví dụ: a = 5, b = 7. Vậy các số chúng ta nên duyệt qua các số chia hết cho 7 là 7, 14, 21, 28, 35. Như vậy, chúng ta giảm được rất nhiều số lần lặp.

Đánh giá: Phương pháp này số lần lặp trong trường hợp xấu nhất là a*b / max(a, b).

#include 
#include 
int main(){
    int a = 5, b = 7, lcm;
    int maxV = a*b;
    int step = std::max(a, b);
    for(int i = step; i <= maxV; i+= step){
        if(i % a == 0 && i % b == 0){
            lcm = i;
            break;
        }
    }
    printf("BCNN(%d, %d) = %d", a, b, lcm);
}

Cách 3: Phân tích thừa số nguyên tố

Sử dụng cách tìm bội chung nhỏ nhất đã học trong toán cấp 2:

1. Bước 1: Phân tích mỗi số ra thừa số nguyên tố.
2. Bước 2: Chọn ra các thừa số nguyên tố chung và riêng.
3. Bước 3: Lập tích các thừa số đã chọn, mỗi thừa số lấy với số mũ lớn nhất của nó. Tích đó chính là BCNN cần tìm.

Cách này thuận tiện cho tính toán trên giấy, tuy nhiên việc thực hiện code phức tạp hơn và tốc độ cũng không quá tốt.

#include 
#include 

Cách 4: Tìm BCNN dựa vào UCLN

Dựa vào sơ đồ khối tìm bội chung nhỏ nhất của 2 số, ta có công thức: BCNN(a, b) = a*b / UCLN(a,b)

Dưới đây là code tham khảo để tìm bội chung nhỏ nhất theo UCLN giống sơ đồ khối phía trên:

#include 
#include 

Cách 5: Sử dụng hàm lcm có sẵn ở C++17

Hàm lcm chỉ có sẵn trong phiên bản C++17, và cách sử dụng rất đơn giản:

#include 
#include 
#include 
using namespace std;
int main(){
    int a = 5, b = 7;
    int ans = lcm(a, b);
    printf("BCNN(%d, %d) = %d", a, b, ans);
}