Bạn đang đọc: ✅ Cách tìm ước chung lớn nhất ⭐️⭐️⭐️⭐️⭐️
5/5 – ( 1 bầu chọn )
nội dung
- 1 Ước chung lớn nhất là gì?
- 2 Cách tìm ước chung lớn nhất
- 3 Những lưu ý khi tìm ước chung lớn nhất
- 4 Tìm ƯỚC CHUNG LỚN NHẤT bằng cách phân tích các số ra thừa số nguyên tố
- 5 Tìm ƯỚC CHUNG dựa vào ƯỚC CHUNG LỚN NHẤT
- 6 Bài tập áp dụng
- 7 Thuật toán tìm ước chung lớn nhất trong C/C++
- 8 Các thuật toán tìm ước chung lớn nhất
Ước chung lớn nhất là gì?
Ước chung lớn nhất ( ƯCLN ) của hai hay nhiều số là số lớn nhất trong tập hợp những ước chung của những số đó .
Trong tiếng Anh, ước chung lớn nhất gọi là greatest common factor ( GCF ) .
Ký hiệu ước chung lớn nhất của a và b là ƯCLN ( a, b ) .
Ví dụ : Tìm ƯCLN ( 24, 16, 32 )
Ư ( 24 ) = { 1, 2, 3, 4, 6, 8, 12, 24 }
Ư ( 16 ) = { 1, 2, 4, 8, 16 }
Ư ( 32 ) = { 1, 2, 4, 8, 16, 32 }
Vậy ƯCLN ( 24, 16, 32 ) = 8
Cách tìm ước chung lớn nhất
Cách 1: Liệt kê các ước chung của các số rồi chọn ra ƯCLN
Để tìm ước chung lớn nhất của những số, ta tìm tập hợp những ước của từng số đó. Sau đó chọn ước chung lớn nhất .
Ví dụ : Tìm Ước chung lớn nhất của hai số tự nhiên 16 và 30 .
Đầu tiên ta tìm tập hợp những ước của 16 và 30 .
Ư ( 15 ) = { 1, 2, 4, 8, 16 }
Ư ( 30 ) = { 1, 2, 3, 5, 6, 10, 15, 30 }
Vậy ƯCLN ( 16,30 ) = 2
Cách 2: Phân tích các số ra thừa số nguyên tố
Bước 1 : Phân tích mỗi số ra thừa số nguyên tố .
Bước 2 : Chọn ra những thừa số nguyên tố chung .
Bước 3 : Lập tích những tích thừa số đã chọn, mỗi thừa số lấy với số mũ nhỏ nhất của nó .
Tích đó là ƯCLN phải tìm .
Ví dụ : Tìm ƯCLN ( 12, 30 )
12 = 2 x 2 x 3
30 = 2 x 3 x 5
Ta có : những thừa số nguyên tố chung là 2 và 3 .
Vậy ƯCLN ( 12, 30 ) = 2 x 3 = 6
Cách 3: Tìm ƯCLN bằng bội chung nhỏ nhất (BCNN) (điều kiện a, b khác 0)
Ước chung lớn nhất của a và b hoàn toàn có thể tính bằng cách lấy tích của a và b chia cho bội chung nhỏ nhất ( BCNN ) của a và b .
Ví dụ : Tìm ƯCLN ( 12, 30 )
B ( 12 ) = { 0, 12, 24, 36, 48, 60, … }
B ( 30 ) = { 0, 30, 60, … }
Ta có : BCNN ( 12,30 ) = 60
Vậy ƯCLN ( 12,30 ) = 12.30 : 60 = 6
Những lưu ý khi tìm ước chung lớn nhất
- Nếu trong các số đã cho có 1 số bằng 1 thì ước chung lớn nhất của các số đó bằng 1.
Ví dụ : ƯCLN ( 1, 55, 95 ) = 1
- Nếu các số đã cho mà không có thừa số nguyên tố chung thì ước chung lớn nhất của số đó là 1.
Ví dụ : Số 5 và 8 không có thừa số nguyên tố chung nên ƯCLN ( 5,8 ) = 1
- Hai hay nhiều số có ước chung lớn nhất bằng 1 được gọi là những số nguyên tố cùng nhau.
Ví dụ : ƯCLN ( 6,35 ) = 1 nên 6 và 35 là hai số nguyên tố cùng nhau .
- Trong các số đã cho, nếu có số nhỏ nhất là ước của các số còn lại thì ước chung lớn nhất của các số đã cho chính là số nhỏ nhất ấy.
Ví dụ : 5 đều là ước của 5 và 15 nên ƯCLN ( 5,15 ) = 5
Tìm ƯỚC CHUNG và ƯỚC CHUNG LỚN NHẤT dựa vào định nghĩa
✨ Tập hợp các ước chung của hai số a và b được ký hiệu là:
ƯC(a,
b)
✨ Tương tự, tập hợp các ước chung của a, b, c được ký hiệu là:
ƯC(a,
b,
c)
Câu hỏi 1:
a) Tìm Ư(12).
b) Tìm Ư(30).
c) Tìm ƯC(12,
30).
Giải
a) Ư(12) = {1; 2; 3; 4; 6; 12}
b) Ư(30) = {1; 2; 3; 5; 6; 10; 15; 30}
c) Các phần tử chung của Ư(12) và Ư(30) là: 1; 2; 3; 6.
Vậy ƯC(12,
30) = {1; 2; 3; 6}
✨ Cách tìm ƯC(a, b) – tập hợp các ước chung của a và b:
- Viết tập hợp các ước của a và ước của b: Ư(a), Ư(b);
- Tìm những phần tử chung của Ư(a) và Ư(b). Đây cũng chính là những phần tử của ƯC(a,
Câu hỏi 2:
a) Tìm ƯC(30,
45).
b) Tìm ƯC(18,
36,
45).
Giải
a) Ta có:
Ư ( 30 ) = { 1 ; 2 ; 3 ; 5 ; 6 ; 10 ; 15 ; 30 }
Ư ( 45 ) = { 1 ; 3 ; 5 ; 9 ; 15 ; 45 }
Các thành phần chung của Ư ( 30 ) và Ư ( 45 ) là : 1 ; 3 ; 5 ; 15 .
Vậy: ƯC(30,
45) = {1; 3; 5; 15}
b) Ta có:
Ư ( 18 ) = { 1 ; 2 ; 3 ; 6 ; 9 ; 18 }
Ư ( 36 ) = { 1 ; 2 ; 3 ; 4 ; 6 ; 9 ; 12 ; 18 ; 36 }
Ư ( 45 ) = { 1 ; 3 ; 5 ; 9 ; 15 ; 45 }
Các thành phần chung của cả ba tập Ư ( 18 ), Ư ( 36 ) và Ư ( 45 ) là : 1 ; 3 và 9 .
Vậy: ƯC(18,
36,
45) = {1; 3; 9}
✨ Ước chung lớn nhất của a và b là số lớn nhất trong tập hợp các ước chung của a và b.
✨ Ước chung lớn nhất của a và b được ký hiệu là:
ƯCLN(a,
b)
Câu hỏi 3:
a) Tìm ƯC(24,
30).
b) Tìm ƯCLN(24,
30).
Giải
a) Ta có:
Ư ( 24 ) = { 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 12 ; 24 }
Ư ( 30 ) = { 1 ; 2 ; 3 ; 5 ; 6 ; 10 ; 15 ; 30 }
Do đó :
ƯC(24,
30) = {1; 2; 3; 6}
b) Số lớn nhất trong tập hợp ƯC(24,
30) vừa tìm được là số 6.
Vậy ƯCLN(24,
30) = 6.
✨ Cách tìm ƯCLN(a, b):
- Tìm ƯC(a,
- Tìm số lớn nhất trong tập hợp ƯC(a,
Câu hỏi 4: Tìm ƯCLN(18,
30).
Giải
Ta có :
Ư ( 18 ) = { 1 ; 2 ; 3 ; 6 ; 9 ; 18 }
Ư ( 30 ) = { 1 ; 2 ; 3 ; 5 ; 6 ; 10 ; 15 ; 30 }
Do đó :
ƯC(18,
30) = {1; 2; 3; 6}
Số lớn nhất trong tập ƯC(18,
30) là 6.
Vậy ƯCLN(18,
30) = 6.
✨ ƯC(a,
b) là một tập hợp, còn ƯCLN(a,
b) là một con số.
✨ Với mọi số tự nhiên a và b, ta có :
ƯCLN(a,
1) = 1;
ƯCLN(a,
b,
1) = 1
✨ Trong những số đã cho, nếu số nhỏ nhất là ước của những số còn lại thì ước chung lớn nhất của những số đã cho chính là số nhỏ nhất ấy .
Nếu a ⋮ b thì ƯCLN(a,
b) = b.
Câu hỏi 5:
a) Tìm ƯCLN(199,
1);
b) Tìm ƯCLN(6,
18).
Giải
a) ƯCLN(199,
1) = 1
b) Vì 18 ⋮ 6 nên ƯCLN(6,
18) = 6.
Tìm ƯỚC CHUNG LỚN NHẤT bằng cách phân tích các số ra thừa số nguyên tố
Sau đây là một cách khác để tìm ước chung lớn nhất, rất đắc dụng khi gặp các số a và b quá lớn hoặc có quá nhiều ước:
✨ Muốn tìm ước chung lớn nhất (ƯCLN) của hai hay nhiều số lớn hơn 1, ta thực hiện ba bước sau:
- Bước 1: Phân tích mỗi số ra thừa số nguyên tố.
- Bước 2: Chọn ra các thừa số nguyên tố chung.
- Bước 3: Lập tích các thừa số đã chọn, mỗi thừa số lấy với số mũ nhỏ nhất của nó. Tích đó là ƯCLN phải tìm.
Câu hỏi 6: Tìm ƯCLN(45,
150)
Giải
Bước 1 : Phân tích 45 và 150 ra thừa số nguyên tố .
- 45 = 32. 5
- 150 = 2. 3. 52
Bước 2 : Chọn ra những thừa số nguyên tố chung, đó là : 3 và 5 .
Bước 3 : Số mũ nhỏ nhất của 3 là 1. Số mũ nhỏ nhất của 5 là 1 .
Vậy: ƯCLN(45,
150) = 3. 5 = 15
Câu hỏi 7: Tìm ƯCLN(56,
140,
168)
Giải
Bước 1 : Phân tích 56 ; 140 và 168 ra thừa số nguyên tố .
- 56 = 23. 7
- 140 = 22. 5. 7
- 168 = 23. 3. 7
Bước 2 : Chọn ra những thừa số nguyên tố chung, đó là : 2 và 7 .
Bước 3 : Số mũ nhỏ nhất của 2 là 2. Số mũ nhỏ nhất của 7 là 1 .
Vậy: ƯCLN(56,
140,
168) = 22. 7 = 28
✨ Sau khi phân tích các số ra thừa số nguyên tố, nếu chúng không có thừa số nguyên tố chung thì ƯCLN của chúng bằng 1.
Câu hỏi 8: Tìm ƯCLN(24,
25)
Giải
Phân tích 24 và 25 ra thừa số nguyên tố :
- 24 = 23. 3
- 25 = 52
Vậy 24 và 25 không có thừa số nguyên tố chung .
Do đó, ƯCLN(24,
25) = 1
Tìm ƯỚC CHUNG dựa vào ƯỚC CHUNG LỚN NHẤT
Tất cả những ước chung ( ƯC ) của hai hay nhiều số đều là ước của ƯCLN của những số đó. Vậy ta có cách tìm ƯC dựa vào ƯCLN như sau :
✨ Muốn tìm ƯC của hai hay nhiều số lớn hơn 1, ta làm hai bước sau:
- Bước 1: Tìm ƯCLN của các số đó.
- Bước 2: Tìm tập hợp các ước của ƯCLN đó. Đây cũng chính là tập hợp phải tìm.
Câu hỏi 9:
a) Tìm ƯCLN(24,
72)
b) Dựa vào câu a, hãy tìm ƯC(24,
72).
Giải
a) Vì 72 ⋮ 24 nên ƯCLN(24,
72) = 24.
b) Ước chung của 24 và 72 là ước của ƯCLN(24,
72).
Vậy: ƯC(24,
72) = Ư(24) = {1; 2; 3; 4; 6; 8; 12; 24}
Câu hỏi 10: Tìm ƯC(72,
180)
Giải
Ta có :
- 72 = 23. 32
- 180 = 22. 32. 5
Do đó :
ƯCLN(72,
180) = 22. 32 = 36
Vậy :
ƯC(72,
180) = Ư(36) = {1; 2; 3; 4; 6; 9; 12; 18; 36}
Xem thêm: ✅ Công thức nguyên hàm ⭐️⭐️⭐️⭐️⭐️
Tóm lược bài học:
✨ Cách tìm ước chung ƯC(a,
b):
- Cách 1: Tìm các phần tử chung của Ư(a) và Ư(b).
- Cách 2: Tìm các ước của ƯCLN(a,
✨ Cách tìm ước chung lớn nhất ƯCLN(a,
b):
- Cách 1: Tìm số lớn nhất trong tập hợp ước chung ƯC(a,
- Cách 2: Phân tích a và b ra thừa số nguyên tố.
Bài tập áp dụng
Bài tập 1: Tìm:
a) ƯCLN(1, 49);
b) ƯCLN(15, 30);
c) ƯCLN(27, 35);
d) ƯCLN(84, 156).
Bài tập 2: Tìm:
a) ƯC(28, 42);
b) ƯC(180, 234).
Các dạng toán về ước chung lớn nhất
Dạng 1: Tìm ước chung lớn nhất của các số cho trước
Dạng này cách làm khá đơn thuần. Học sinh chỉ cần vận dụng 3 bước của cách tìm ước chung lớn nhất là hoàn toàn có thể giải một cách thuận tiện .
Ví dụ 1: Tìm ước chung lớn nhất của (12, 30)
Ta có : 12 = 2 × 2 x 3
30 = 2 x 3 x 5
Ta có những thừa sừa số nguyên tố chung là 2 và 3
=> Ước chung lớn nhất ( UCLN ) ( 12, 30 ) = 2 x 3 = 6
Ví dụ 2: Tìm UCLN (8, 9); UCLN (8, 12, 15); UCLN (24, 16, 8)
UCLN ( 8, 9 ) = 1
UCLN ( 8, 12, 15 ) = 1
UCLN ( 24, 16, 8 ) = 8
*** Cách tìm ước chung
- Muốn tìm ước chung của các số đã cho ta có thể tìm các ước của ƯCLN của các số đó.
- Như vậy, tập hợp các ước chung của các số đã cho là tập hợp các ước của ƯCLN của các số đó.
Ví dụ: Tìm ƯCLN rồi tìm các ước chung của :
a ) 16 và 24 ; b ) 180 và 234 ; c ) 60, 90 và 135 .
Giải
16 = 24 ; 24 = 23.3 ;
ƯCLN ( 16,24 ) = 23 = 8 .
Các ước chung của 16 và 24 chính là những ước của 8. Đó là 1 ; 2 ; 4 và 8 .
Đáp số :
ƯCLN ( 180, 234 ) = 18. Các ước chung là 1, 2, 3, 6, 9, 18 .
ƯCLN ( 60, 90, 135 ) = 15. Các ước chung là : 1, 3, 5, 15 .
Dạng 2: Bài toán đưa về việc tìm ước chung lớn nhất của hai số
Ở dạng này, học viên cần nghiên cứu và phân tích đề bài, suy luận để đưa về việc tìm ƯCLN của hai hay nhiều số .
Ví dụ:
Tìm số tự nhiên a lớn nhất biết rằng 420 chia hết cho a và 700 chia hết cho a .
Giải
Theo đề bài a phải là ƯCLN của 420 và 700 .
ƯCLN ( 420, 700 ) = 140 .
Vậy a = 140 .
Dạng 3: Tìm các ước chung của hai hay nhiều số thỏa mãn điều kiện cho trước
Phương pháp giải
– Tìm ƯCLN của hai hay nhiều số cho trước ;
– Tìm những ước của ƯCLN này ;
– Chọn trong số đó những ước thỏa mãn nhu cầu điều kiện kèm theo đã cho .
Ví dụ:
Mai và Lan mỗi người mua cho tổ mình một số ít hộp bút chì màu. Mai mua 28 bút, Lan mua 36
bút. Số bút trong những hộp bút đều bằng nhau và số bút trong mỗi hộp lớn hơn 2 .
a ) Gọi số bút trong mỗi hộp là a. Tìm quan hệ giữa số a với mỗi số 28, 36, 2 .
b ) Tìm số a nói trên .
c ) Hỏi Mai mua bao nhiêu hộp bút chì màu ? Lan mua bao nhiêu hộp bút chì màu ?
Trả lời
a ) a là ước của 28, a là ước của 36, a > 2 .
b ) a ∈ ƯC ( 28, 36 ) và a > 2. Từ đó tìm được a = 4.0
c ) Mai mua 7 hộp bút, Lan mua 9 hộp bút .
Bài tập vận dụng
Bài 1: Tìm các ước chung lớn hon 20 của 144 và 192 .
Giải
ƯCLN ( 144, 192 ) = 48 .
Ư ( 48 ) = { 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 12 ; 16 ; 24 ; 48 } .
Các ước của 48 lớn hơn 20 là 24 và 48 .
Vậy những ước chung lớn hon 20 của 144 và 192 là 24 và 48 .
Bài 2:.
Tìm số tự nhiên x, biết rằng 112 chia hết cho x, 140 chia hết cho x và 10 < x < 20 .
Hướng dẫn
x ∈ ƯC ( 12, 140 ) và 10 < x < 20. ƯCLN ( 112, 140 ) = 28 . Đáp số : x = 14 .
Bài 3:
Lan có một tấm bìa hình chữ nhật size 75 cm và 105 cm. Lan muốn cắt tấm bìa thành
những mảnh nhỏ hình vuông vắn bằng nhau sao cho tấm bìa được cắt hết, không còn thừa mảnh
nào. Tính độ dài lớn nhất của cạnh hình vuông vắn ( số đo cạnh của hình vuông vắn nhỏ là 1 số ít tự
nhiên với đơn vị chức năng là xăng-ti-mét ) .
Giải
Để tấm bìa được cắt hết thành những mảnh nhỏ hình vuông vắn bằng nhau thì độ dài mỗi cạnh
của hình vuông vắn phải là ước chung của 75 và 105. Do đó độ dài lớn nhất của cạnh hình vuông vắn
( tính bằng cm ) là ƯCLN ( 75,105 ), tức là 15 cm .
Bài 4: Một người chủ có một chuồng thỏ. Người chủ muốn cho những con thỏ trong chuồng ăn, mà ông chỉ có 6 cây súp lơ và 8 củ cà rốt. Ông muốn mỗi con thỏ đều được ăn cả súp lơ và cà rốt. Và số lượng súp lơ và cà rốt ăn được phải bằng nhau. Thức ăn cũng không được để thừa. Vậy số thỏ là bao nhiêu để có thể ăn đều như mong muốn của ông chủ.
Ta vận dụng kỹ năng và kiến thức về ước chung lớn nhất để giải bài tập .
Số thỏ tối đa không được lớn hơn 6 để bảo vệ số thỏ không ăn thừa hay thiếu số súp lơ .
Trong bài toán này ta sẽ tìm ước chung lớn nhất của 6 và 8, bởi tất cả chúng ta muốn tìm ra số thỏ mà trong đó hoàn toàn có thể chia đều 6 cây súp lơ và 8 củ cà rốt cho chúng .
Ta có : 6 = 2 x 3
8 = 2 x 4
Vậy ước chung lớn nhất của hai số là 2. Số thỏ trong chuồng sẽ là 2 con. Mỗi con ăn được 3 cây súp lơ và 4 củ cà rốt .
Bài 5:
Tìm ƯCLN của :
a ) 56 và 140 ; b ) 24, 84, 180 ;
c ) 60 và 180 ; d ) 15 và 19 .
Giải
a ) 56 = 23.7 ; 140 = 22. 5.7 .
ƯCLN ( 56,140 ) = 22.7 = 28 .
Đáp số : b ) 12 ; c ) 60 ; d ) 1 .
Bài 6:
Tìm ƯCLN của :
a ) 16, 80, 176 ; b ) 18, 30, 77 .
Đáp số
a ) 16 ; b ) 1
Bài 7:
Tìm số tự nhiên a lớn nhất biết rằng 420 chia hết cho a và 700 chia hết cho a .
Giải
Theo đề bài a phải là ƯCLN của 420 và 700 .
ƯCLN ( 420, 700 ) = 140 .
Vậy a = 140 .
Bài 8:
Đội văn nghệ của một trường có 48 nam và 72 nữ về một huyện để màn biểu diễn. Muốn Giao hàng
đồng thời tại nhiều khu vực, đội dự tính chia thành những tổ gồm cả nam và nữ, số nam
được chia đều vào những tổ, số nữ cũng vậy .
Có thể chia được nhiều nhất thành bao nhiêu tổ ?
Khi đó mỗi tổ có bao nhiêu nam, bao nhiêu nữ ?
Đáp số
Số tổ nhiều nhất là ƯCLN ( 48,72 ) = 24. Khi đó mỗi tổ có 2 năm, 3 nữ .
Bài 9: Tìm a, b biết a + b = 42 và [a, b] = 72.
Lời giải: Gọi d = (a, b) => a = md; b = nd với m, n thuộc Z+; (m, n) = 1.
Không mất tính tổng quát, giả sử a ≤ b => m ≤ n .
Do đó : a + b = d ( m + n ) = 42 ( 1 )
[ a, b ] = mnd = 72 ( 2 )
=> d là ước chung của 42 và 72 => d thuộc { 1 ; 2 ; 3 ; 6 } .
Lần lượt thay những giá trị của d vào ( 1 ) và ( 2 ) để tính m, n ta thấy chỉ có trường hợp d = 6 => m + n = 7 và mn = 12 => m = 3 và n = 4. ( thỏa mãn nhu cầu những điều kiện kèm theo của m, n ). Vậy d = 6 và a = 3.6 = 18, b = 4.6 = 24
Bài 10: Tìm a, b biết a – b = 7, [a, b] = 140.
Lời giải : Gọi d = ( a, b ) => a = md ; b = nd với m, n thuộc Z + ; ( m, n ) = 1 .
Do đó : a – b = d ( m – n ) = 7 ( 1 ’ )
[ a, b ] = mnd = 140 ( 2 ’ )
=> d là ước chung của 7 và 140 => d thuộc { 1 ; 7 } .
Thay lần lượt những giá trị của d vào ( 1 ’ ) và ( 2 ’ ) để tính m, n ta được hiệu quả duy nhất :
d = 7 => m – n = 1 và mn = 20 => m = 5, n = 4
Vậy d = 7 và a = 5.7 = 35 ; b = 4.7 = 28 .
Các Dạng Toán:
Dạng 1: Tìm Ước chung lớn nhất của các số cho trước:
Phương pháp: Thực hiện quy tắc ba bước đề tìm UCLN của hai hay nhiều số.
Ví dụ 1: Tìm UCLN của:
a) 16, 80, 176
b) 18, 30, 77.
Giải:
a) 16 = 2^4
80 = 5.2^4
176 = 11.2^4
Thừa số chung là 2^4 = 16 Đây là UCLN của 3 số đã cho.
b) 18 = 2.3^2
30 = 2.3.5
77 = 11.7
Thừa số chung là 1 –> Đây cũng là UCLN cần tìm.
Ví dụ 2: Tìm UCLN rồi tìm các ước chung của:
a) 16 và 24
b) 180 và 234
c) 60, 90 và 135
Giải:
a) 16 = 2^4
24 = 3.2^3
–> UCLN(16,24) = 2^3 = 8.
Các ước chung của 16 và 24 chính là các ước của 8. Đó là: 1; 2; 4; 8.
Phần b và c gia sư môn toán lớp 6 chỉ đưa ra đáp án còn cách giải cụ thể các em hãy tự làm và tham khảo thêm hướng dẫn của các gia sư nhé.
b) UCLN(180,234). Các ước chung là: 1; 2; 3; 6; 9; 18.
c) UCLN(60, 90, 135). Các ước chung là: 1; 3; 5; 15.
Dạng 2: Bài toán đưa về việc tìm UCLN của hai hay nhiều số.
Phương pháp:
Phân tích đề bài, suy luận để đưa về việc tìm UCLN của hai hay nhiều số.
Ví dụ: Tìm số tự nhiên a lớn nhất biết rằng 420 | a và 700 | a.
Giải:
Theo đề bài a phải là UCLN(420,700) mà UCLN(420, 700) = 140. Vậy a = 140.
Dạng 3: Tìm các ước chung của hai hay nhiều số thỏa mãn điều kiện cho trước:
Phương pháp:
- Tìm UCLN của hai hay nhiều số cho trước;
- Tìm các ước của UCLN này;
- Chọn trong các số đó các ước thỏa mãn điều kiện đã cho.
Ví dụ: Tìm các ước chung lớn hơn 20 của 144 và 192.
Hướng dẫn giải:
UCLN(144, 192) = 48.
Ước của 48 = {1; 2; 3; 4; 6; 8; 12; 24; 48}
Các ước của 48 lớn hơn 20 là 24 và 48.
Vậy các ước chung lớn hơn 20 của 144 và 192 là 24 và 48.
Thuật toán tìm ước chung lớn nhất trong C/C++
Định nghĩa ước chung lớn nhất
Ước chung lớn nhất ( GCD – Greatest Common Divisor ) của 2 số nguyên a và b là số nguyên lớn nhất d thỏa mãn nhu cầu đặc thù cả a và b đều chia hết cho d .
Các thuật toán tìm ước chung lớn nhất
Dưới đây là 1 số ít cách thường được sử dụng để xử lý bài toán tìm ước chung lớn nhất của hai số .
Cách 1. Tìm UCLN sử dụng phép trừ
Đây là sơ đồ của thuật toán này
Thuật toán tìm ước chung lớn nhất sử dụng phép trừ
Code minh họa
Giải thích:
Cách 2. Tìm UCLN sử dụng phép chia dư
Sơ đồ thuật toán tựa như như cách 1. Chỉ đổi khác phép trừ sang phép chia dư .
Code minh họa
Cách 3. Tìm UCLN sử dụng giải thuật Euclid
Cho a, b là hai số nguyên ( giả sử a ≥ b ), để tìm ước chung lớn nhất của hai số a và b ta cần thực thi chia a cho b được thương q và số dư r ( r ≥ 0 ) tức là a = b * q + r, khi đó ta có :
Cách 4. Tìm UCLN sử dụng hàm có sẵn của C++
Để hoàn toàn có thể sử dùng hàm tìm ucln trong C + + ta cần thêm thư viện algorithm .
Ví dụ minh họa :
Tổng kết tất cả cách cách trên trong 1 chương trình.
✅ Phương pháp học ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️
✅ Lớp 6 ⭐ ️ ⭐ ️ ⭐ ️ ⭐ ️ ⭐
🔢 GIA SƯ TOÁN LỚP 6
Source: https://thcsbevandan.edu.vn
Category : Phương pháp học tập