: Ước chung lớn nhất của hai số a và b là số lớn nhất mà a và b cùng chia hết cho số đó.
Ví dụ: số 30 và số 45 cùng chia hết cho 1; 5; 15 thì 15 là ước chung lớn nhất của 30 và 45. Để
tìm ước chung lớn nhất của a và b có nhiều cách, tuy nhiên cách nhanh nhất là sử dụng thuật
toán do nhà toán học Ơclit tìm ra cách đây hơn 4000 năm. Thuật toán tìm UCLN của hai số
a và b như sau:
Bước 1:Nếu b=0 thì ước chung lớn nhất là a
Bước 2: a=b; b=r (r là số dư của a chia cho b) quay lại bước 1
Ví dụ: Tìm ƯCLN(72, 56)= UCLN (56,16)=UCLN(16,8)=UCLN(8,0)=8
Nhập vào hai số a và b, lập trình tìm UCLN theo thuật toán trên
Loga
Sinh Học lớp 12
