Liệt kê các số Smith nhỏ hơn n trong Python

Số Smith là một số tự nhiên có các đặc điểm sau:

1. Tổng các chữ số của số đó bằng tổng các chữ số của các thừa số nguyên tố của nó.
2. Số Smith không phải là số nguyên tố.

Ví dụ: Số 85 là một số Smith vì tổng các chữ số là 8 + 5 = 13, và 85 có thể phân tích thành 5 × 17, với tổng các chữ số của 5 và 17 cũng là 13.

Dưới đây là một cài đặt đơn giản của thuật toán tìm số Smith trong Python:

def prime_factors(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def digit_sum(n):
    return sum(int(digit) for digit in str(n))

def is_smith_number(n):
    if n < 4:
        return False
    factors = prime_factors(n)
    if len(factors) == 1:
        return False
    return digit_sum(n) == sum(digit_sum(factor) for factor in factors)

# Ví dụ sử dụng:
for i in range(1, 1001):
    if is_smith_number(i):
        print(i)

Trong đoạn mã trên, ta sử dụng hai hàm phụ:

• prime_factors(n): Nhận đầu vào là một số nguyên n và trả về danh sách các thừa số nguyên tố của n.
• digit_sum(n): Nhận đầu vào là một số nguyên n và trả về tổng các chữ số của n.

Hàm chính is_smith_number(n) kiểm tra xem số n có phải là số Smith hay không. Đầu tiên, nó kiểm tra xem số n có nhỏ hơn 4 hay không, vì các số nhỏ hơn 4 không được coi là số Smith. Tiếp theo, nó tìm các thừa số nguyên tố của n bằng cách sử dụng hàm prime_factors(n). Sau đó, nó so sánh tổng các chữ số của n với tổng các chữ số của các thừa số nguyên tố. Nếu hai tổng này bằng nhau, số n được coi là số Smith và hàm trả về True. Ngược lại, hàm trả về False.

Trong ví dụ sử dụng, ta tìm và in ra tất cả các số Smith từ 1 đến 1000. Bạn có thể thay đổi phạm vi để tìm các số Smith trong khoảng số khác nhau.