viết thuật toán Tìm ước chung lớn nhất của 2 số nguyên dương a và b.

Ư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ố. Nhưng có 1 phương pháp tối ưu nhất là sử dụng thuật toán Euclid dựa trên dãy liên tiếp các phép chia có dư.

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(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

Gửi bn:

-Xác định bài toán

+In: 2 số nguyen dương a và b

+Out: ucln(a,b);

-Xây dựng thuật toán

+Bước 1: nhập 2 số nguyen dương a và b

+Bước 2: nếu a>b thì a:=a-b

+Bước 3: ngược lại thì b:=b-a

+Bước 4: Nếu a<>b thì quay lại bước 2

+Bước 5: ucln:=a;

+Bước 6: Xuất ucln

+Bước 7: Kết thúc

chúc bn học tốt

XIn hay nhất