Cách Tìm ước Chung Lớn Nhất

3.3/5 - (3 bình chọn)

Mục Lục

Toggle

• Ước chung lớn nhất là gì?
• 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
  • Cách 2: Phân tích các số ra thừa số nguyên tố
  • Cách 3: Tìm ƯCLN bằng bội chung nhỏ nhất (BCNN) (điều kiện a, b khác 0)
• Những lưu ý khi tìm ước chung lớn nhất
  • Tìm ƯỚC CHUNG và ƯỚC CHUNG LỚN NHẤT dựa vào định nghĩa
• 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ố
• Tìm ƯỚC CHUNG dựa vào ƯỚC CHUNG LỚN NHẤT
• Bài tập áp dụng
• Thuật toán tìm ước chung lớn nhất trong C/C++
• Các thuật toán tìm ước chung lớn nhất
  • Cách 1. Tìm UCLN sử dụng phép trừ
  • Cách 2. Tìm UCLN sử dụng phép chia dư
  • Cách 3. Tìm UCLN sử dụng giải thuật Euclid
  • Cách 4. Tìm UCLN sử dụng hàm có sẵn của C++

Ướ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 các ước chung của các 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 các số, ta tìm tập hợp các ướ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 các ướ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 các thừa số nguyên tố chung.

Bước 3: Lập tích các 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ó: các 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 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, b).

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 phần tử 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 phần tử 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, b);
• Tìm số lớn nhất trong tập hợp ƯC(a, b). Đó chính là ƯCLN(a, b)

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 các số đã cho, nếu 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.

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 các 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 các 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ả các ước chung (ƯC) của hai hay nhiều số đều là ước của ƯCLN của các 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}

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

✨ 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, b).
• 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 giản. Học sinh chỉ cần áp dụng 3 bước của cách tìm ước chung lớn nhất là có thể giải một cách dễ dàng.

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ó các 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à các ướ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 sinh cần 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 các ước của ƯCLN này ;

– Chọn trong số đó các ước thỏa mãn điều kiện đã cho.

Ví dụ:

Mai và Lan mỗi người mua cho tổ mình một số hộp bút chì màu. Mai mua 28 bút, Lan mua 36

bút. Số bút trong các 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 các ướ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 kích thước 75cm và 105cm. Lan muốn cắt tấm bìa thành

các mảnh nhỏ hình vuông 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 (số đo cạnh của hình vuông nhỏ là một số tự

nhiên với đơn vị là xăng-ti-mét).

Giải

Để tấm bìa được cắt hết thành các mảnh nhỏ hình vuông bằng nhau thì độ dài mỗi cạnh

của hình vuông 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

(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 áp dụng 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 để đảm bảo 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 chúng ta muốn tìm ra số thỏ mà trong đó 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 để biểu diễn. Muốn phục vụ

đồng thời tại nhiều địa điểm, đội dự định chia thành các tổ gồm cả nam và nữ, số nam

được chia đều vào các 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 các 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 các điều kiện 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 các giá trị của d vào (1’) và (2’) để tính m, n ta được kết 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, 176b) 18, 30, 77.Giải:a) 16 = 2^480 = 5.2^4176 = 11.2^4Thừa số chung là 2^4 = 16 Đây là UCLN của 3 số đã cho.b) 18 = 2.3^230 = 2.3.577 = 11.7Thừ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à 24b) 180 và 234c) 60, 90 và 135Giải:a) 16 = 2^424 = 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 tính chất 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à một số cách thường được sử dụng để giải quyết 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

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ương tự như cách 1. Chỉ thay đổi 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 hiện 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++

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