# 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: .

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))