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 1 ). 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, 4937775 is a Smith number.
Task: Write a program to check whether a given integer is a Smith number.
Input:
- There will be only one line of input: n(0<n<109), the number which needs to be checked.
Output:
- print 1 if the number is a Smith number.
- print 0 if the number is not a Smith number.