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