Hackerrank - Identify Smith Numbers Solution

A Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding ). The first few such numbers are 4, 22, 27, 58, 85, 94 and 121

Example:
378 = 2 x 3 x 3 x 3 x 7
So, its prime factors are 2, 3, 3, 3 and 7
The sum of its digits is (3+7+8)=18.
The sum of the digits of its factors is (2+3+3+3+7)=18.

Similarly,  is a Smith number.
, and the sum of its digits is the same as the sum of the digits of its prime factors: .

Task:
Write a program to check whether a given integer is a Smith number.

Input Format

There will be only one line of input: N, the number which needs to be checked.

Constraints:
0 < N < 2,147,483,647 (max value of an integer of the size of  bytes)

Output Format

1 if the number is a Smith number.
0 if the number is a not Smith number.

Sample Input

378

Sample Output

1

Explanation

Its prime factors are 2, 3, 3, 3, and 7.
The sum of its digits is (3+7+8)=18.
The sum of the digits of its factors is (2+3+3+3+7)=18.

Solution in Python

from math import sqrt


def getPrime(n):
    """
    Function to get the first prime factor of a number 
    Example: getPrime(12) = 2

    Args:
        n (integer): number whose prime factor is to be found

    Returns:
        integer : prime factor of the number
    """

    if n % 2 == 0:
        return 2
    for i in range(3, int(sqrt(n))+1, 2):
        if n % i == 0:
            return i
    return n


def solve(n):
    sum_of_factor_digits = 0
    sum_of_digits = sum(map(int, str(n)))
    while n != 1:
        # get the first prime factor of n
        prime_factor = getPrime(n)
        # while number is divisible by the prime factor, add the sum of the digits of the prime factor 
        while n % prime_factor == 0:
            sum_of_factor_digits += sum(map(int, str(prime_factor)))
            # divide the number by the prime factor
            n = n//prime_factor

    return 1 if sum_of_factor_digits == sum_of_digits else 0


n = int(input())
print(solve(n))