Tìm bội chung nhỏ nhất của 2 số - Chương trình tìm BCNN của 2 số

Tìm bội chung nhỏ nhất của 2 số – Chương trình tìm BCNN 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 lập trình. Trong bài viết này, Nguyễn Văn Hiếu sẽ cùng các bạn đi tìm các phương pháp khác nhau để giải bài tập tìm bội chung nhỏ nhất của 2 số nguyên dương. Mỗi cách làm đều sẽ có ý tưởng rõ ràng, cách triển khai và code tìm bcnn minh họa theo cách đó.

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

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

Theo Wikipedia,

Trong số học, bội số chung nhỏ nhất (hay còn gọi tắt là bội chung nhỏ nhất, viết tắt là BCNN, tiếng Anh: least common multiple hoặc lowest common multiple (LCM) hoặc smallest common multiple) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả a và b.[1] Tức là nó có thể chia cho a và b mà không để lại số dư. Nếu a hoặc b là 0, thì không tồn tại số nguyên dương chia hết cho a và b, khi đó quy ước rằng LCM(a, b) là 0.

Định nghĩa trên đôi khi được tổng quát hoá cho hơn hai số nguyên dương: Bội chung nhỏ nhất của a1,…, an là số nguyên dương nhỏ nhất là bội số của a1,…, an.

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

Ta có một số nhận xét như sau: Theo định nghĩa, BCNN của 2 số a và là số nhỏ nhất chia hết cho cả 2 số a và b. Như vậy, Nếu gọi lcm = BCNN(a, b); Khi đó, ta có thể biết chắc chắn rằng max(a, b) <= lcm <= a*b.

Nắm rõ tính chất này, ta có thể đi vào một số thuật toán tìm BCNN như sau:

C1. Lặp tăng dần cho tới khi tìm được BCNN

Cách này ý tưởng khá là đơn giản, ta chỉ cần tiến hành lặp từ nhỏ tới lớn các số trong đoạn từ [max(a, b),a*b](bao gồm cả 2 đầu mút). Số đầu tiên chia hết cho cả a và b sẽ là BCNN của a và b.

Đánh giá: Cách này trong trường hợp xấu nhất sẽ cần a*b – max(a, b) lần lặp. Vẫn với ý tưởng này nhưng sẽ được tối ưu ở C2

Chạy thử xem sao:

C2. 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ả 2 số này. Do đó, ta có thể chỉ cần duyệt qua các số chia hết cho 1 số(hoặc a, hoặc b). Nhưng để tối ưu, bạn 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 rồi.

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

Chạy thử chương trình:

C3. Phân tích thừa số nguyên tố

Sử dụng cách tìm bcnn đã học trong toán cấp 2:

Bước 1: Phân tích mỗi số ra thừa số nguyên tố.
Bước 2: Chọn ra các thừa số nguyên tố chung và riêng.
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 đó là BCNN cần tìm.

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

Lưu ý: Để code ngắn gọn nhất, mình sẽ sử dụng các cấu trúc STL của C++ và tính năng for auto của C++11

Cách này các bạn có thể tham khảo và bạn có thể tối ưu thêm. Mình sẽ không giải thích sâu vì thực tế, thuật toán tìm bcnn này triển khai khá rườm rà và không tối ưu.