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:**

N = 666.

Prime factors are 2, 3, 3, 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.

Write a program to input a number and check if it is a smith number or not.

**Program:**

```
import java.io.*;
class Smith{
public static void main(String args[])
throws IOException{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
System.out.print("N = ");
int n = Integer.parseInt(br.readLine());
if(isComposite(n)){
int sum1 = sumOfDigits(n);
int sum2 = sumOfDigitsOfPrimeFactors(n);
if(sum1 == sum2)
System.out.println(n + " is a Smith Number.");
else
System.out.println(n + " is not a Smith Number.");
}
else
System.out.println(n + " is not a Smith Number.");
}
public static boolean isComposite(int n){
int f = 0;
for(int i = 1; i <= n; i++)
if(n % i == 0)
f++;
if(f > 2)
return true;
return false;
}
public static int sumOfDigits(int n){
int s = 0;
for(int i = n; i != 0; i /= 10)
s += i % 10;
return s;
}
public static int sumOfDigitsOfPrimeFactors(int n){
int s = 0;
int f = 2;
while(n != 1){
while(n % f == 0 && f <= n){
s += sumOfDigits(f);
n /= f;
}
f++;
}
return s;
}
}
```