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.

C4. Tìm BCNN của 2 số dựa vào UCLN

Dưới đây là sơ đồ khối tìm bội chung nhỏ nhất của 2 số:

so-doi-khoi-tim-boi-chung-nho-nhat-cua-2-so
Sơ đồ khối tìm BCNN của 2 số

Khi đó, ta có công thức: BCNN(a, b) = a*b / UCLN(a,b)

Các bạn có thể xem các thuật toán tìm UCLN của 2 số, 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:

C5. Sử dụng hàm lcm có sẵn ở C++17

Hàm này chỉ có ở C++17, và cách sử dụng rất đơn giản:

 

avatar
2 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Nguyễn Văn HiếuYuuHuy Tuan Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Huy Tuan
Guest
Huy Tuan

I’ve been browsing online more thann 3
hoսrs today, yet I never found any interesting article like yours.

It is pretty worth enough for me. Personally, if ɑlⅼ web owners and bloggers made
good content as yoou did, the internet will be a lot moгe usefսl
than ever before.

Yuu
Guest
Yuu

Mọi thứ thật là có giá trị. Lâu rồi mới thấy một web trực tuyến mà lại trực quan và hay như vậy. Mình có cảm giác mỗi lần nhìn thấy các article là mình lại muốn click vào đọc tiếp vậy.
Cảm ơn rất nhiều vì đã tạo ra web bổ ích như vậy :))