Checking whether a number is a Smith number I have created a Java program to check if the number entered by the user is a Smith number (a number whose sum of digits equals the sum of the digits of its prime factorization). The program works fine but takes too long to check numbers like 4937775. How do I reduce the time taken by it to execute? 

import java.util.*; 
class check
{
    static boolean a;
    static boolean checkprime(long n)
    {
        int i, factors= 0; 
        for(i = 1;i&lt;=n ;i++)
        {
            if(n%i==0)
                factors++;
        }
        if(factors == 2)
            return true;
        else
            return false; 
    }

    static long sumfinder(long  n)
    {
        long  sum = 0; 
        while(n!=0)
        {
            sum = sum + n%10; 
            n= n/10; 
        }
        return sum; 
    }

    static boolean checksmith(long  n)
    {
        long  sum = 0; 
        if(checkprime(n)== true)
        { 
            System.out.println(n + " is a prime number ");
            return false; 
        }
        else
        {
            System.out.println(n + " is not  a prime number ");
            //generate prime factors: 
            long  num = n; 

            outer: 
            for(long  i = 1; i&lt;= num ; i++)
            {
                if(checkprime(i)== true)
                {

                    if(num%i== 0)
                    {
                        sum= sum+ sumfinder(i); 
                        num = num/i; 
                        i = 1;
                        if (num == 1)
                        {
                            break outer; 
                        }
                    }
                }
            }
        }

        System.out.println(sum);
        System.out.println(sumfinder(n));

        if (sumfinder(n)== sum)

            return true; 

        else
            return false;
    }

    static void display()throws InputMismatchException
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number");
        long  n = sc.nextInt(); 
        if(checksmith(n)== true)
        {
            System.out.println("Smith number");

        }
        else
            System.out.println("Not a Smith number");
    }

    public static void main(String [] args)
    {
        display(); 
    }
}
class check



Java naming convention is that class names should start with an uppercase letter. Check is also not very informative: what does it check?




    static boolean a;



Is this used anywhere?




    static boolean checkprime(long n)



Again, Java naming convention is that (a) camel-case should be used (checkPrime instead of checkprime); (b) Boolean-valued properties should generally have names beginning is (isPrime instead of checkPrime). In this case isPrime reads quite naturally in context (e.g. if (isPrime(n)) ...).




        int i, factors= 0; 
        for(i = 1;i&lt;=n ;i++)
        {
            if(n%i==0)
                factors++;
        }
        if(factors == 2)
            return true;
        else
            return false; 



Why give i such a wide scope?

Why use factors at all? If you find a divisor which is not 1 or n you can return false immediately.

What's going on with the whitespace in for(i = 1;i&lt;=n ;i++)? The semicolon separates expressions: I can't understand why you'd want whitespace inside the expression i = 1 but not after the semicolon which separates the 1 from i&lt;=n.

There are much faster ways to test primality. Aside from the comments made in another answer about only testing up to sqrt(n), look around for discussion on BPSW or just use BigInteger.isProbablePrime.




    static long sumfinder(long  n)



Again, names. If the name of a method is a noun, I expect it to describe the object returned: but the long returned is not a sum-finder. It's the sum. I suggest that a better name for this method would be digitSum.




    {
        long  sum = 0; 
        while(n!=0)
        {
            sum = sum + n%10; 
            n= n/10; 
        }
        return sum; 
    }



I understand this to be at the level of throwaway code rather than production: if it were production code, I'd expect to see either some code to handle the case n &lt; 0 or a comment to explain why that is unnecessary.




    static boolean checksmith(long  n)



See previous comments on names.

Existing answers propose some better ways to write the body of this method; I want to focus as much on general points of style as on algorithms, although I do have one or two points to add there too.




        long  sum = 0;



Which sum? There are two relevant sums, right?


        if(checkprime(n)== true)



== true is a crime against KISS.


            System.out.println(n + " is a prime number ");



That's an unexpected side effect.


            //generate prime factors:



I'm not sure what exactly the scope of this comment is, but I wouldn't describe the following loop as generating prime factors.


            outer:



?? There's no inner loop, so what purpose does this label serve?


            for(long  i = 1; i&lt;= num ; i++)



That should strike terror into the heart of anyone who wants their program to terminate in a reasonable time. There are three possible cases: (a) i could perfectly well be an int; (b) i gets incremented by more than 1 elsewhere; (c) this loop will execute more than \$2^{31}\$ times. Here it's not case (b), so which of the other two is it?

(Aside: the rewrites correctly observe that you only need to go up to sqrt(n), but if n is a long that could still be about \$2^{31.5}\$. It might be worth looking at faster factorisation methods, starting with Pollard's rho).


                if(checkprime(i)== true)
                {
                    if(num%i== 0)



In addition to previous comments, why check whether i is prime? That check is slower than the num % i check, and if the second check succeeds then the first one must also for basic number-theoretic reasons.


                    {
                        sum= sum+ sumfinder(i); 



Here you could have an early-abort if the partial digit sum of prime factors already exceeds the digit sum of the original number. That same idea carries over into the suggested rewrites of the method.


        if (sumfinder(n)== sum)

            return true; 

        else
            return false;



Those six lines could be simplified to return sumfinder(n) == sum;




    static void display()throws InputMismatchException



Um. If the method is called display, I expect it to do output. Why is it throwing an input-related exception?