Tìm UCLN,BCNN

Hix, maruko quên hết mấy cái này rùi. Mọi người nhắc lại hộ maruko & yoci nhé. Thanks!(Gửi nhanh nhé)

Đây nè bạn. Vampire cũng quên mất rồi. Giờ phải tìm lại

Tính ước chung lớn nhất
ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố, chẳng hạn để tìm ƯCLN(18,84), ta phân tích 18 = 2·32 và 84 = 22·3·7 và nhận xét rằng các thừa số chung lớn nhất của hai số này là 2·3; do đó ƯCLN(18,84) = 6. Trên thực tế phương pháp này chỉ dùng cho các số nhỏ; việc phân tích các số lớn ra thừa số nguyên tố mất rất nhiều thời gian.
Đối với các số to, ta dùng giải thụât Ơ-clit (Euclid) để tìm:

Ví dụ:
Tính ước số chung lớn nhất của 91 và 287.

Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:

287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)
Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:

91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)
Cuối cùng ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

Còn về BCNN, theo trí nhớ của mình thì hình như là:
Bước 1: Phân tích 2 số ra dạng nguyên tố (8=2^3; 6=2*3).
Bước 2: Nhóm các thừa số chung lấy số mũ cao nhất với các thừa số không chung. Nhân chúng với nhau.
Bước 3: Kết quả phép nhân là BCNN cần tìm.
(VD: BCNN(8;6)=2^3*3)
Áp dụng tương tự với UCLN, nhưng ở bước 2 khác ở chỗ lấy số mũ nhỏ nhất, và không lấy thừa số không chung.

Test thử cho mình nhé. Thanks!

Này, tui có quên đâu mà bảo là tui quên!

Tưởng thank người ta một cái. Ai ngờ ....

Thì thank cho một cái, có mất gì đâu !