Bài toán tìm Ước chung lớn nhất và Bội chung nhỏ nhất của hai số

Bài toán liên quan đến ước chung có thể là bài toán tìm ước chung lớn nhất (Greatest Common Divisor – GCD) hoặc bài toán tìm bội chung nhỏ nhất (Least Common Multiple – LCM) của hai hoặc nhiều số.

1. Tìm ước chung lớn nhất (GCD):
Bạn có thể sử dụng thuật toán Euclid để tìm GCD của hai số. Dưới đây là một ví dụ sử dụng đệ quy để tính GCD của hai số:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# Ví dụ sử dụng:
num1 = 12
num2 = 18
result = gcd(num1, num2)
print(result)  # Output: 6
```

Trong ví dụ này, chúng ta tạo một hàm `gcd()` nhận vào hai số `a` và `b`. Sử dụng thuật toán Euclid, chúng ta kiểm tra nếu `b` bằng 0, thì GCD của `a` và `b` là `a`. Nếu không, chúng ta đệ quy gọi hàm `gcd()` với tham số `b` và `a % b`.

Cuối cùng, hàm trả về GCD của hai số (`a` và `b`).

Trong ví dụ trên, GCD của 12 và 18 là 6.

2. Tìm bội chung nhỏ nhất (LCM):
Bạn có thể sử dụng công thức để tính LCM dựa trên GCD của hai số. Dưới đây là một ví dụ:

def lcm(a, b):
    return (a * b) // gcd(a, b)

# Ví dụ sử dụng:
num1 = 12
num2 = 18
result = lcm(num1, num2)
print(result)  # Output: 36
```

Trong ví dụ này, chúng ta tạo một hàm `lcm()` nhận vào hai số `a` và `b`. Sử dụng công thức: LCM(a, b) = (a * b) / GCD(a, b), chúng ta tính tích của `a` và `b`, và chia cho GCD của `a` và `b` (được tính bằng hàm `gcd()`).

Cuối cùng, hàm trả về LCM của hai số (`a` và `b`).

Trong ví dụ trên, LCM của 12 và 18 là 36.

Hy vọng rằng những thông tin này có thể giúp bạn giải quyết bài toán liên quan đến ước chung.

 

Trả lời