Cần giúp đỡ về bài toán tìm ước chung của 2 số

Không đụng tới lập trình, nếu cho bạn 2 số nguyên bất kì thì bạn tìm ƯC của 2 số đó như thế nào

ví dụ: a=6, b=24
mình sẽ phân tích a=6=3*2
vì b lớn hơn a thì mình chỉ cần biết a và làm như cách trên thì mình sẽ có ước chung của 2 số là 1,2,3,6

Mình chỉ không làm thế nào để áp dụng thuật toán này vào phần lập trình của mình nên bạn có thể gợi ý cho mình môt chút được không bạn?

Đúng rồi, mình lại hỏi thêm 1 câu nữa, tại sao bạn biết 6=2×3 mà không phải là cặp số khác

vì 6 chia hết cho 2 và 6 cũng chia hết cho 3

Thực ra phân tích ra thừa số nguyên tố là việc rất khó. Cách đó chỉ giải được với số nhỏ thôi.

Ta chỉ cần vận dụng tính chia hết như sau: d | a && d | b => d | (a +/- b).

bạn có thể giải thích thuật toán d | a && d | b => d | (a +/- b). này giúp mình, mình vẫn chưa hiểu rõ lắm. Tks bạn

Kí hiệu d | a là “d chia hết a”. Vậy a = k1d theo phép chia Euclid. Tương tự b = k2d. Vậy a+/-b = (k1+/-k2)*d, hay d | (a+/-b).

Giờ phải đi chậm chậm

KMTTQ, gs a >= b > 0. Vừa c/m xong ta có:
d | a && d | b => d | (a-b) && d | b (thuận) với mọi d
và với mọi d1 s.c. d1 | (a-b) && d1 | b thì d1 | a && d1 | b (đảo)
Vậy d với d1 như nhau => max {d} = max {d1}.
Vậy ucln(a-b, b) = ucln(a, b).

Thuật toán sẽ phải dừng khi a-b = 0, do b>0 nên a-b < a.

d có vai trò gì trong hàm này vậy bạn vì theo mình nghĩ là a,b sẽ là 2 số mình cần tim ước chung nếu xuất hiện d thì nó có thể là gì ?

bạn ơi mình có để để bài là tìm ước chung của 2 số a và b chứ không phải ucln bạn ơi. Bạn xem lại giúp mình

Không phải tất cả ước chung đều chia hết ước chung lớn nhất sao?

Vậy nếu mình muốn tìm tất cả các ước chung của 2 số ví dụ là a=24, b=6 thì mình phải làm gì bạn?

đơn giản nhất là từ 1->3 số nào mà cả 24 và 6 đều chia hết thì đó là ước chung, nhớ xét thêm trường hợp 24 có chia hết cho 6 luôn nữa không

Tính ra ucln bằng 6 rồi chia thử cho đến sqrt().

d có vai trò gì trong hàm này vậy bạn vì theo mình nghĩ là a,b sẽ là 2 số mình cần tim ước chung nếu xuất hiện d thì nó có thể là gì ?

Câu kết luận nằm ở đây:

Vậy d với d1 như nhau => max {d} = max {d1}.
Vậy ucln(a, b) = ucln(a-b, b).