Viết chương trình nhập vào 2 số a và b, Tìm ước chung lớn nhất và bội chung nhỏ nhất của chúng.

Xin chào các bạn hôm nay mình sẽ hướng dẫn các bạn cách viết chương trình tìm ước chung lớn nhất và bội chung nhỏ nhất của 2 số. Ở đây mình sẽ hướng dẫn các bạn 3 cách từ cơ bản đến nâng cao.

CÁCH 1 : 
Đầu tiên, là cách cơ bản nhất. Đó là dùng vòng lặp WHILE, rồi lấy số lớn trừ nhỏ cho đến khi chúng bằng nhau. Cách này dành cho những bạn học yếu, đỡ phải suy nghĩ nhiều. Tuy nhiên cách này có hạn chế là nếu mà 2 số chênh nhau quá lớn thì nó sẽ lặp rất nhiều lần, điều này không quan trọng đối với các bạn học sinh, nhưng nếu đi sâu vào chuyên ngành thì việc làm này sẽ tốn dung lượng bộ nhớ.

Ví dụ tìm UCLN và BCNN của 11 và 3 (bằng phương pháp nhìn ta thấy được UCLN của 2 số này là 1 và BCNN là 33).
Thì với phương pháp này :
- UCLN : ta sẽ lấy 11 - 3 = 8, 8 - 3 =5, 5 - 3 = 2; 3 - 2 = 1; 2 - 1 = 1. Lúc này chúng đã bằng nhau và bằng 1. Và 1 cũng chính là UCLN.
-BCNN : bằng tích của 2 số chia cho UCLN lấy phần nguyên.
+ Tích của 2 số là 11x3 = 33
+ Chia 1 lấy phần nguyên là bằng 33.
(Ví dụ 21 chia 2 lấy phần nguyên là bằng 10, chúng ta chỉ lấy số ở trước dấu phẩy còn ở sau dấu phẩy thì vứt đi nhé)

Ta có code hoàn thiện sau :

var x,y,UCLN,BCNN:integer;
begin
readln(x,y);
BCNN:=x*y;
While x<>y do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
write(UCLN,' ',BCNN);
end.

CÁCH 2 :  Ta dùng toán Euclide (Ơ-cờ-lít). Để tối ưu hơn số lần lặp ở cách 1, thì ta sử dụng mod chia lấy phần dư.

var x,y,UCLN,BCNN,t:integer;
begin
readln(x,y);
BCNN:=x*y;
t:= y mod x;
While t <> 0 do
Begin
t:= x MOD y;
x:= y;
y:= t;
End;
ucln:=x;
BCNN:=BCNN div UCLN;
write(UCLN,' ',BCNN);
end.

CÁCH 3 :  Cách này hơn nâng cao 1 tý, tuy nhiên nếu bạn nào có nghiên cứu về đệ quy thì nó cũng dễ ấy mà,

var x,y,UCLN,BCNN,t:integer;
function ucln(x,y:integer):integer;
begin
if x = y then
ucln:=x
else if x > y then 
ucln:=ucln(x mod y,y)
else 
ucln:=ucln(x, y mod x); 
end;
var x,y:integer;
begin
readln(x,y);
write('Ước chung lớn nhất là: ', UCLN(x,y), ' Bội chung nhỏ nhất là: ', (x*y) div UCLN(x,y));
end.