Python - Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của 2 số nguyên dương

Tìm ước số chung lớn nhất và bội số chung nhỏ nhất trong Python

Bạn đã từng gặp phải tình huống cần tìm ước số chung lớn nhất (USCLN) và bội số chung nhỏ nhất (BSCNN) của hai số nguyên dương? Trong bài viết này, chúng ta sẽ cùng tìm hiểu cách giải quyết vấn đề này bằng lập trình python' class='hover-show-link replace-link-1687'> ngôn ngữ lập trình python .

Hình ảnh minh họa

Định nghĩa

USCLN (Ước số chung lớn nhất) của hai số nguyên dương a và b là một số k lớn nhất, sao cho cả a và b đều chia hết cho k. Trong khi đó, BSCNN (Bội số chung nhỏ nhất) của hai số nguyên dương a và b là một số h nhỏ nhất, sao cho h chia hết cho cả a và b.

Lời giải

Một phương pháp đơn giản để tìm USCLN của a và b là duyệt từ số nhỏ hơn trong hai số a và b cho đến 1. Khi gặp số nào đó mà cả a và b đều chia hết cho nó, thì đó chính là USCLN của a và b. Tuy nhiên, phương pháp này chưa phải là hiệu quả nhất.

Vào thế kỷ 3 TCN, nhà toán học Euclid đã phát minh ra một giải thuật tìm USCLN của hai số nguyên dương rất hiệu quả, được gọi là giải thuật Euclid. Ý tưởng của giải thuật này là: giả sử a lớn hơn b, khi đó việc tính USCLN của a và b sẽ được đưa về bài toán tính USCLN của a mod b và b, vì USCLN(a, b) = USCLN(a mod b, b).

Khi đã tìm được USCLN, việc tìm BSCNN của hai số nguyên dương a và b khá đơn giản. Khi đó, BSCNN(a, b) = (a b) / USCLN(a, b*).

1. Tìm USCLN và BSCNN của 2 số nguyên dương trong Python bằng giải thuật Euclid

Dưới đây là một ví dụ sử dụng giải thuật Euclid để giải quyết bài toán tìm USCLN và BSCNN của hai số nguyên dương a và b.

def tim_uscln(a, b):     while b != 0:         temp = a % b         a = b         b = temp     return a  def tim_bscnn(a, b):     return (a * b) / tim_uscln(a, b)  a = 15 b = 20  uscln = tim_uscln(a, b) bscnn = tim_bscnn(a, b)  print("USCLN của {} và {} là: {}".format(a, b, uscln)) print("BSCNN của {} và {} là: {}".format(a, b, bscnn))

Kết quả:

USCLN của 15 và 20 là: 5 BSCNN của 15 và 20 là: 60

2. Tìm USCLN và BSCNN của 2 số nguyên dương trong Python bằng cách khác

Kết quả:

USCLN của 15 và 20 là: 5 BSCNN của 15 và 20 là: 60

Giải thích hoạt động của chương trình trên: Trong chương trình này, chúng ta nhập vào hai số 15 và 20, sau đó chương trình thực thi hàm tim_uscln() với các bước như sau:

1. Gán giá trị biến temp1 = 15 và temp2 = 20.
2. Kiểm tra điều kiện bên trong vòng lặp while: Vì 15 != 20, nên sẽ thực thi lệnh bên trong vòng lặp while. Lúc này, 15 < 20, nên lệnh bên trong else sẽ được thực thi và temp2 = 5.
3. Quay lại bước 2, kiểm tra điều kiện bên trong vòng lặp while: Vì 15 != 5, nên sẽ thực thi lệnh bên trong vòng lặp while. Lúc này, 15 > 5, nên lệnh bên trong if sẽ được thực thi và temp1 = 10.
4. Quay lại bước 3, kiểm tra điều kiện bên trong vòng lặp while: Vì 10 != 5, nên sẽ thực thi lệnh bên trong vòng lặp while. Lúc này, 10 > 5, nên lệnh bên trong if sẽ được thực thi và temp1 = 5.
5. Quay lại bước 3, kiểm tra điều kiện bên trong vòng lặp while: Vì 5 == 5, nên sẽ không thực thi lệnh bên trong vòng lặp while. Vòng lặp kết thúc, trả về giá trị USCLN = 5.

Dựa vào USCLN tìm được, chúng ta tính BSCNN là (a * b) / USCLN.

Chúc mừng! Bạn đã thành công trong việc tìm ước số chung lớn nhất và bội số chung nhỏ nhất của hai số nguyên dương bằng ngôn ngữ lập trình Python. Hy vọng bài viết này đã giúp bạn hiểu rõ về cách thức hoạt động của hai khái niệm quan trọng này.