Có nhiều thuật toán để tìm ước chung lớn nhất (hay GCD), nhưng đơn giản nhất đó chính là thuật toán Euclid. Sau đây mình sẽ trình bày cách tư duy cho bài này
B1: Xác định đầu vào (input) là hai số a,b nguyên dương
B2: Viết thuật toán để có được đầu ra như đề bài yêu cầu là ƯCLN
Thuật toán Euclid
Trong khi b khác 0 thì:
tạm = b
b = a mod b
a = tạm
kết quả sẽ là a
B3: Xuất kết quả (output) là ƯCLN
Đây là mã nguồn chương trình tìm ước chung lớn nhất bằng Pascal
uses crt;
var tam, a, b: integer;
begin
clrscr;
writeln("Nhap vao so a: ");
readln(a);
writeln("Nhap vao so b: ");
readln(b):
while a <> b do
begin
tam = b;
b = a mod b;
a = tam;
end;
writeln("UCLN la: ", a);
readln;
end.