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, 121…

Example 1
Consider the number 666.
Prime factors are 2, 3, 3 and 37.
Sum of the digits = 6 + 6 + 6 = 18.
Sum of the digits of the factors = 2 + 3 + 3 + (3 + 7) = 18.
Hence, 666 is a Smith Number.

Example 2
Consider the number 4937775.
Prime factors are 3, 5, 5 and 65837.
Sum of the digits = 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42.
Sum of the digits of the factors = 3 + 5 + 5 + (6 + 5 + 8 + 3 + 7) = 42.
Hence, 4937775 is a Smith Number.

Write a Java program to input a number and display whether the number is a Smith Number or not.

SAMPLE DATA
INPUT: 94
OUTPUT: Smith Number
INPUT: 666
OUTPUT: Smith Number
INPUT: 999
OUTPUT: Not a Smith Number

import java.util.Scanner;
class Smith{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the number: ");
        int num = Integer.parseInt(in.nextLine());
        int sum = sumOfDigits(num);
        int sumPrime = 0;
        int p = 2;
        while(num > 1){
            while(num % p == 0){
                sumPrime += sumOfDigits(p);
                num /= p;
            }
            p++;
        }
        if(sum == sumPrime)
            System.out.println("It is a Smith Number!");
        else
            System.out.println("It is not a Smith Number.");
    }
    public static int sumOfDigits(int num){
        int sum = 0;
        while(num > 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}