Bội chung nhỏ nhất – Lập trình tìm BCNN trong Python và Scratch

Bội chung nhỏ nhất – Lập trình tìm BCNN trong Python và Scratch

Bội chung nhỏ nhất của hai hay nhiều số là gì?

Bội chung nhỏ nhất (least common multiple – LCM) của hai hoặc nhiều số (tự nhiên) là số tự nhiên nhỏ nhất chia hết cho tất cả các số đó.

Phương pháp tìm BCNN

Để tìm bội chung nhỏ nhất của hai số, ta có thể sử dụng một số phương pháp như:

• Phương pháp tương đương: Phân tích hai số thành các thừa số nguyên tố và lấy các thừa số nguyên tố chung với mũ lớn nhất.
• Sử dụng ước chung lớn nhất: Tính bội chung nhỏ nhất bằng công thức LCM(a, b) = |a * b| / GCD(a, b), trong đó GCD(a, b) là ước chung lớn nhất của hai số a và b.

Để tìm bội chung nhỏ nhất của nhiều số, ta có thể áp dụng phương pháp tương tự. Ta tính bội chung nhỏ nhất của từng cặp số trong dãy và tiếp tục tính bội chung nhỏ nhất của kết quả với số tiếp theo cho đến khi duyệt qua tất cả các số.

Dưới đây là một ví dụ về cách lập trình tính bội chung nhỏ nhất của hai hoặc nhiều số trong Python:

Tìm BCNN của 2 số trong Python:

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

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

def lcm_of_multiple(numbers):
    result = numbers[0] 


    for i in range(1, len(numbers)):
        result = lcm(result, numbers[i] 






)
    return result

# Tính bội chung nhỏ nhất của hai số
num1 = int(input("Nhập số thứ nhất: "))
num2 = int(input("Nhập số thứ hai: "))
result = lcm(num1, num2)
print("Bội chung nhỏ nhất của", num1, "và", num2, "là:", result)

Tìm BCNN của nhiều số trong Python:

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

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

def lcm_of_multiple(numbers):
    result = numbers[0] 


    for i in range(1, len(numbers)):
        result = lcm(result, numbers[i] 



)
    return result

# Tính bội chung nhỏ nhất của nhiều số
num_list = [] 






n = int(input("Nhập số lượng số: "))
for i in range(n):
    num = int(input("Nhập số thứ " + str(i+1) + ": "))
    num_list.append(num)
result = lcm_of_multiple(num_list)
print("Bội chung nhỏ nhất của các số là:", result)

Trong chương trình trên, chúng ta định nghĩa các hàm gcd, lcm và lcm_of_multiple. Hàm gcd tính ước chung lớn nhất của hai số bằng thuật toán Euclid tương tự như trước đó. Hàm lcm tính bội chung nhỏ nhất của hai số bằng công thức LCM(a, b) = |a * b| / GCD(a, b). Hàm lcm_of_multiple tính bội chung nhỏ nhất của nhiều số bằng cách tính lần lượt bội chung nhỏ nhất của từng cặp số trong dãy.

Chương trình yêu cầu người dùng nhập vào hai số hoặc số lượng số và các số tương ứng. Sau đó, chương trình sử dụng các hàm lcm hoặc lcm_of_multiple để tính bội chung nhỏ nhất. Cuối cùng, chương trình in ra kết quả.

Tìm BCNN của 2 số trong Scratch