Tìm USCLN(a, b) va BSCNN(a, b)
Ví dụ: USCLN(18, 24) = 6 và BSCNN(18, 24) = 72
Yêu cầu: Input: a, b là 2 số tự nhiên.
Output: USCLN và BSCNN của a và b
Một số lưu ý:
- Nếu i là ước số của a và b thì a và b đồng thời chia hết cho i
- Luôn luôn có tối thiểu một USCLN của a và b là 1.
- Nếu i là USCLN thì i là ước số nhỏ hơn cả a lẫn b và gần a, b nhất.
Như vậy, nếu sử dụng một vòng lặp để kiểm tra a,b có đồng thời chia hết cho i hay không thì i là USCLN khi:
+ i là USC (a, b cùng chia hết cho i) cuối cùng nếu i lặp từ 1 đến a (hoặc b).
+ i là USC (a, b cùng chia hết cho i) đầu tiên nếu lặp từ a (hoặc b) quay về 1.
- BSCNN(a, b) = a * b / (USCLN(a, b)
Hướng dẫn:
Bài toán được thực hiện qua 3 bước cụ thể như sau:
- Thông báo nhập liệu, và nhập dữ liệu vào cho a và b
- Tiến hành tính USCLN(a, b):
Sử dụng vòng lặp for, lặp từ a lùi về 1.
Kiểm tra nếu a, b đều chia hết cho i thì gọi lệnh break để dừng vòng lặp.
==> i là USC đầu tiên gần a, b nhất ==>USCLN
- Xuất kết quả của USCLN(a, b) , BSCNN (a, b) ra màn hình.
Chương trình:
Program USCLN;
Use crt;
Var a , b :integer; // Khai bao bien su dung
Begin
Write(‘Nhap vao so a:’); // Thong bao nhap lieu
Readln(a); // Nhap gtri a (voi &a, la lay d/c bien a,)
Write(‘Nhap vao so b:’); // Thong bao nhap lieu
Readln(b); // Nhap gtri b (voi &b, la lay d/c bien b,)
For i:=a downto 1 do
If ((a mod i = 0) and (b mod i = 0)) then // Kiem tra a, b co chia het
Break;
Writeln(‘USCLN (‘,a,’,’,b,’):’, i); // Xuat ket qua USCLN(a, b)
Writeln(‘BSCNN (‘,a,’,’,b,’):’, a*b div i); // Xuat ket qua USCLN(a, b)
Readln;
End.