3
\$\begingroup\$

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<=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<= 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(); 
    }
}
\$\endgroup\$
0
5
\$\begingroup\$
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<=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<=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<=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 < 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<= 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?

\$\endgroup\$
1
  • \$\begingroup\$ Excellent answer! Thanks. I'll try to follow the guidelines and conventions you mentioned. \$\endgroup\$
    – Archer
    Dec 21 '17 at 17:16
2
\$\begingroup\$

To factorize an integer, you only need to loop over factors between 2 and sqrt(num). If n is a prime, num will be equal to n now. If num is not 1 now, it is a prime factor too.

import java.util.*;
class Check {
    static long sumDigits(long n) {
        long sum = 0;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    static boolean checkSmith(long n) {
        long sum = 0, num = n;
        for (long i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                // i is a prime here
                sum += sumDigits(i);
                num /= i;
            }
        }
        if (n == num && n > 1) {
            System.out.println(n + " is a prime number");
            return false;
        }
        System.out.println(n + " is not a prime number");
        if (num > 1) {
            // num is a prime here
            sum += sumDigits(num);
        }

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

        return sumDigits(n) == sum;
    }

    static void display() throws InputMismatchException {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number:");
        long n = sc.nextLong();
        if (checkSmith(n))
            System.out.println("Smith number");
        else
            System.out.println("Not a Smith number");
    }

    public static void main(String[] args) {
        display();
    }
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Just be careful about arithmetic overflow with expressions such as i * i <= num. Consider 1.0 * i * i <= num instead, to use a type with larger range. \$\endgroup\$ Jun 19 '18 at 15:37
  • \$\begingroup\$ @TobySpeight True. However, double has less precision. Why is it correct (especially for square of large primes)? I'd use && i <= 3037000499 instead. \$\endgroup\$ Jun 20 '18 at 18:51
  • \$\begingroup\$ In the cases where you lose the precision (and it matters), I believe you end up with 1.0 * i * i == num when mathematically i² ≆ num, so the loop continues at least as far as it should (it doesn't matter if we perform an extra iteration - we won't hit another factor). Your suggestion of testing that i is less than the root of a maximal long is probably better (though I'd want to give a meaningful name to the constant), or you could test i <= Math.sqrt(num) - but you'd probably want to cache that root and update it when you change num. \$\endgroup\$ Jun 21 '18 at 7:00
  • \$\begingroup\$ Oh, and if you use sqrt(), you probably want to round or ceil it before use! \$\endgroup\$ Jun 21 '18 at 7:23
  • \$\begingroup\$ It's probably a good idea to add if (n <= 1) return; at the start of the function, so we correctly reject negative numbers and 0 and 1 (which are neither prime nor composite), and the prime test can simply be if (n==num). \$\endgroup\$ Jun 21 '18 at 7:37
0
\$\begingroup\$

A few ideas for improvment:

  1. In checkprime, you don't have to loop from 1 to n, looping from 1 to sqrt(n) is enough.

  2. The outer loop is very inefficient. First, every time you find a factor, you start from the beginning looking for more factors, invoking checkprime on number which you already checked. Second, I wouldn't bother checking checkprime on any number from 1 to n, I would do so for divisors.

a more efficient loop would be:

 for(long  i = 1; i<= num ; i++)
    {
        if(num%i== 0 && checkprime(i))
        {
           sum= sum+ sumfinder(i); 
           num = num/i; 
           if (num == 1)
           {
               break outer; 
           }
        }
        i--; //check same factor again
    }
\$\endgroup\$
2
  • \$\begingroup\$ I made the changes you told me to but it still takes too much time. \$\endgroup\$
    – Archer
    Dec 21 '17 at 6:54
  • 1
    \$\begingroup\$ Why call checkprime on the divisor? It's guaranteed to return true, because if i is composite then you have already have factored all of its prime divisors out of num. \$\endgroup\$ Dec 21 '17 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.