Em của bạn Nam đang học về cách rút gọn phân số. Biết rằng để rút gọn một phân số, ta chia và tử số và mẫu số cho ước chung lớn nhất (ƯCLN) của chúng. Hãy viết một chương trình giúp em ấy rút gọn phân số dưới dạng a b, với a và b là hai số nguyên dương cho trước.
Gợi ý: Để tìm ƯCLN của hai số tự nhiên a và b, ta có thể sử dụng thuật toán sau:
Nếu b>0, thì ƯCLN(a,b)=ƯCLN(b,a%b)
Nếu b=0, thì ƯCLN(a,0)=a