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

#1

Mình đang làm bài tập về tìm ước chung của 2 số. Xong mở rộng thêm tìm ước chung lớn nhất của 2 số đó. Mình đã làm được phần tìm ước chung lớn nhất của 2 số nhưng đến phần tìm ước chung thì lại pó tay mong các bạn giúp đỡ!

image.png569×654 15.9 KB

#2

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

1 Like
#3

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

#4

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?

#5

Đú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

#6

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

#7

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).

1 Like
#8

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

#9

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

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

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.

1 Like
#10

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ì ?

#11

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

#12

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

1 Like
#13

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?

#14

đơ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

1 Like
#15

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

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

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?