Tìm bội chung nhỏ nhất của hai hay nhiều số tự nhiên trong Python và Scratch

Bội chung nhỏ nhất (LCM – Least Common Multiple) của hai số tự nhiên ab là một số nguyên dương nhỏ nhất mà cả ab đều chia hết cho nó mà không để lại phần dư.

Để tìm bội chung nhỏ nhất (LCM – Least Common Multiple) của hai số tự nhiên ab trong Python, bạn có thể sử dụng công thức sau:

LCM(a, b) = (a * b) / GCD(a, b)

Trong đó, GCD(a, b)ước chung lớn nhất của ab.

Tìm bội chung nhỏ nhất của hai số tự nhiên trong Python

Cách 1: Sử dụng thư viện Math













import math

# Định nghĩa hàm tính LCM
def lcm(a, b):
    return (a * b) // math.gcd(a, b)

# Nhập hai số tự nhiên từ người dùng
a = int(input("Nhập số tự nhiên a: "))
b = int(input("Nhập số tự nhiên b: "))

# Tính LCM của a và b và in kết quả
result = lcm(a, b)
print("Bội chung nhỏ nhất của", a, "và", b, "là:", result)

Cách 2: Không sử dụng thư viện

















# Định nghĩa hàm tính GCD bằng thuật toán Euclid
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Định nghĩa hàm tính LCM không sử dụng thư viện
def lcm(a, b):
    return (a * b) // gcd(a, b)

# Nhập hai số tự nhiên từ người dùng
a = int(input("Nhập số tự nhiên a: "))
b = int(input("Nhập số tự nhiên b: "))

# Tính LCM của a và b và in kết quả
result = lcm(a, b)
print("Bội chung nhỏ nhất của", a, "và", b, "là:", result)

Trong ví dụ này, chúng ta định nghĩa hai hàm gcd(a, b)lcm(a, b) để tính GCD và LCM tương ứng. Hàm gcd(a, b) sử dụng thuật toán Euclid để tính GCD của ab. Hàm lcm(a, b) sử dụng công thức LCM = (a * b) / GCD(a, b) để tính LCM của ab bằng cách gọi hàm gcd(a, b) và sau đó tính toán LCM.

Read:   Thuật toán vét cạn - Minh họa Tìm tất cả các dãy con của một dãy số

Cuối cùng, chúng ta nhập hai số từ người dùng, tính LCM của chúng và in kết quả lên màn hình.

Tìm bội chung nhỏ nhất của hai số tự nhiên trong C++






























#include <iostream>

// Hàm tính GCD bằng thuật toán Euclid
unsigned int gcd(unsigned int a, unsigned int b) {
    while (b != 0) {
        unsigned int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Hàm tính LCM
unsigned int lcm(unsigned int a, unsigned int b) {
    unsigned int gcd_result = gcd(a, b);
    return (a * b) / gcd_result;
}

int main() {
    unsigned int a, b;  // Hai số tự nhiên a và b
    std::cout << "Nhập số tự nhiên a: ";
    std::cin >> a;  // Nhập số tự nhiên a từ người dùng
    std::cout << "Nhập số tự nhiên b: ";
    std::cin >> b;  // Nhập số tự nhiên b từ người dùng

    unsigned int result = lcm(a, b);
    std::cout << "Bội chung nhỏ nhất của " << a << " và " << b << " là: " << result << std::endl;

    return 0;
}

Tìm bội chung nhỏ nhất của nhiều số tự nhiên trong Python

Cách 1: Sử dụng hàm và itertools































from math import gcd
from functools import reduce
from itertools import combinations

# Hàm tính LCM của hai số
def lcm(a, b):
    return a * b // gcd(a, b)

# Hàm tính LCM của nhiều số tự nhiên
def lcm_multiple(numbers):
    return reduce(lcm, numbers)

# Danh sách các số tự nhiên bạn muốn tính LCM
numbers = [12, 18, 24, 36] 





# Tính LCM của danh sách các số
result = lcm_multiple(numbers)
print("Bội chung nhỏ nhất của các số là:", result)

Cách 2: Sử dụng vòng lặp và hàm GCD



























from math import gcd

# Hàm tính LCM của hai số
def lcm(a, b):
    return a * b // gcd(a, b)

# Hàm tính LCM của nhiều số tự nhiên
def lcm_multiple(numbers):
    result = numbers[0] 

    for num in numbers[1:] 




:
        result = lcm(result, num)
    return result

# Danh sách các số tự nhiên bạn muốn tính LCM
numbers = [12, 18, 24, 36] 





# Tính LCM của danh sách các số
result = lcm_multiple(numbers)
print("Bội chung nhỏ nhất của các số là:", result)

Cách 3: Không dùng thư viện

Để tính bội chung nhỏ nhất (LCM – Least Common Multiple) của nhiều số tự nhiên mà không sử dụng thư viện trong Python, bạn có thể sử dụng thuật toán Euclid để tính ước chung lớn nhất (GCD) và sau đó sử dụng công thức LCM = (a * b) / GCD(a, b) lặp lại cho từng cặp số. Dưới đây là cách thực hiện:




































# Hàm tính GCD bằng thuật toán Euclid
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Hàm tính LCM của nhiều số tự nhiên
def lcm_multiple(numbers):
    if len(numbers) < 2:
        return None  # Không có cách tính LCM nếu chỉ có một số hoặc không có số nào
        
    result = numbers[0] 

    for num in numbers[1:] 




:
        result = (result * num) // gcd(result, num)
    return result

# Danh sách các số tự nhiên bạn muốn tính LCM
numbers = [12, 18, 24, 36] 








# Tính LCM của danh sách các số
result = lcm_multiple(numbers)
if result is not None:
    print("Bội chung nhỏ nhất của các số là:", result)
else:
    print("Không có cách tính LCM với số lượng số này.")

Trong ví dụ này:

  • Chúng ta định nghĩa hai hàm gcd(a, b)lcm_multiple(numbers) để tính GCD và LCM tương ứng. Hàm gcd(a, b) sử dụng thuật toán Euclid để tính GCD của ab, và hàm lcm_multiple(numbers) tính LCM của nhiều số tự nhiên trong danh sách numbers.
  • Hàm lcm_multiple kiểm tra số lượng số trong danh sách numbers. Nếu danh sách chỉ có một số hoặc không có số nào, thì không có cách tính LCM và trả về None. Nếu danh sách có ít nhất hai số, chúng ta sử dụng vòng lặp để tính LCM của từng cặp số và tích hợp nó vào kết quả.
  • Cuối cùng, chúng ta nhập danh sách các số tự nhiên bạn muốn tính LCM, tính LCM của chúng và in kết quả lên màn hình.
Read:   Giáo trình tự học Python và C++ từ cơ bản tới nâng cao
Hình đại diện của người dùng

admin

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *