Số Smith là một số tự nhiên có các đặc điểm sau:
- 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ó.
- 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ênn
và trả về danh sách các thừa số nguyên tố củan
.digit_sum(n)
: Nhận đầu vào là một số nguyênn
và trả về tổng các chữ số củan
.
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.