Thuật toán tìm UCLN, BCNN của 2 số nguyên trong Python

Thuật toán Euclid để tìm ước chung lớn nhất (UCLN) và công thức tính bội chung nhỏ nhất (BCNN) là hai phương pháp quan trọng trong toán học và lập trình. Thuật toán Euclid giúp xác định UCLN của hai số bằng cách sử dụng cách tiếp cận đệ quy, giảm dần vấn đề về kích thước của các số. Công thức tính BCNN sử dụng thông tin từ UCLN, với quy luật đơn giản là BCNN bằng tích của hai số chia cho UCLN tương ứng. Cả hai thuật toán này đều được triển khai một cách hiệu quả trong Python và là công cụ quan trọng trong việc giải quyết các vấn đề liên quan đến số học và thuật toán.

Thuật toán Euclid

Đầu vào: Hai số nguyên dương a và b.

Bước 1: Gọi a là số lớn hơn trong hai số, b là số nhỏ hơn. Nếu không, hoán đổi a và b.

Bước 2: Chia a cho b và lấy phần dư r.

Bước 3: Nếu r bằng 0, kết thúc thuật toán và kết quả là b, ước chung lớn nhất của a và b.

Bước 4: Nếu r không bằng 0, thay thế a bằng b, b thay bằng r, và quay lại Bước 2.

Thuật toán sẽ kết thúc khi phần dư r bằng 0, tại thời điểm đó số b sẽ là ước chung lớn nhất của hai số ban đầu a và b.

Code tham khảo:

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

result = gcd(12, 18)
print(result)  # Kết quả là 6

Thuật toán phân giải

Cách này dựa trên việc phân tích số thành các thừa số nguyên tố và tìm các thừa số chung của hai số.

• Phân tích a và b thành các thừa số nguyên tố.

• Tìm các thừa số chung của hai số này và nhân chúng lại với nhau.

Code tham khảo:

import math

# Tìm tất cả các thừa số nguyên tố của một số
def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:
        factors.append(n)
    return factors

# Tìm GCD của hai số sử dụng phân giải
def gcd_by_prime_factorization(a, b):
    a_factors = prime_factors(a)
    b_factors = prime_factors(b)
    
    gcd = 1
    i = 0
    j = 0
    
    while i < len(a_factors) and j < len(b_factors):
        if a_factors[i] == b_factors[j]:
            gcd *= a_factors[i]
            i += 1
            j += 1
        elif a_factors[i] < b_factors[j]:
            i += 1
        else:
            j += 1
            
    return gcd

# Sử dụng hàm để tính GCD
a = 48
b = 18
result = gcd_by_prime_factorization(a, b)
print(f"GCD của {a} và {b} là {result}")

Sử dụng hàm có sẵn để tìm UCLN

Sử dụng thư viện math

Thư viện math trong Python cung cấp hàm gcd() để tìm UCLN của hai hoặc nhiều số nguyên.

import math

result = math.gcd(12, 18)
print(result)  # Kết quả là 6

Sử dụng thư viện numpy

Nếu bạn đang làm việc với mảng các số và muốn tìm GCD của chúng, thư viện numpy cũng cung cấp hàm gcd().

import numpy as np

numbers = np.array([12, 18, 24])
result = np.gcd.reduce(numbers)
print(result)  # Kết quả là 6

Tìm Bội chung nhỏ nhất

Việc tìm BCNN của hai hay nhiều số chúng ta cũng có thể sử dụng công thức: BCNN(a, b) = (a * b) // UCLN(a, b) hoặc dùng thư viện math.

Sử dụng thư viện math

import math

a = 12
b = 18

lcm_result = math.lcm(a, b)
print(f"LCM của {a} và {b} là {lcm_result}")

Sử dụng công thức

import math

# Tính GCD (ước chung lớn nhất) của hai số
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Tính LCM (bội chung nhỏ nhất) của hai số
def lcm(a, b):
    return (a * b) // gcd(a, b)

a = 12
b = 18

lcm_result = lcm(a, b)
print(f"LCM của {a} và {b} là {lcm_result}")