Smith Number Check

Determine if a composite number's digit sum equals the digit sum of its prime factors.

prime factors digit sum number theory

A **Smith number** is a composite number where the sum of its digits equals the sum of the digits of its prime factors (including multiplicity). For example, 22 is a Smith number because 2+2 = 4 and its prime factors are 2 and 11, giving 2 + (1+1) = 4. Note: 1 is not considered a Smith number (it is not composite). Your task is to implement the function `is_smith(n: int) -> bool` that returns `True` if `n` is a Smith number, and `False` otherwise. The function should handle positive integers up to 10^6.

Constraints

Input n is an integer with 1 ≤ n ≤ 1,000,000. The expected time complexity is O(sqrt(n) log n) or better.

Example

>>> is_smith(22)
True
>>> is_smith(666)
True
>>> is_smith(7)
False
>>> is_smith(1)
False

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

First check if n is composite (not prime and n > 1).

Compute the sum of digits of n and separately the sum of digits of all its prime factors, accounting for multiplicity.

To factorize, try dividing by 2, then odd numbers up to sqrt(n). For each factor, repeatedly divide and add its digit sum.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.