Sum of the digits is prime or not

Question

Puzzle Description:

A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky?

How can I improve performance of the following code?

import java.util.Scanner;

public class lucky_num {

    public static void main(String[] args) {

        lucky_num sr = new lucky_num();
        Scanner scanner = new Scanner(System.in);
        int no_cases = scanner.nextInt();
        for (int i = 0; i < no_cases; i++) {
            System.out.println(sr.solve(scanner.nextLong(), scanner.nextLong()));
        }
    }

    private int solve(long l, long m) {
        int count = 0;
        for (long i = l; i <= m; i++) {
            if (logic(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean logic(long i) {
        return (isSUM(i) && isSUMsq(i));
    }

    private boolean isSUMsq(long i) {
        int sum = 0;
        while (i > 9) {
            long k = i % 10;
            i = i / 10;
            sum += k * k;
        }
        sum += i * i;
        return (isPrime(sum));
    }

    private boolean isSUM(long i) {
        int sum = 0;
        while (i > 9) {
            long k = i % 10;
            i = i / 10;
            sum += k;
        }
        sum += i;
        return (isPrime(sum));
    }

    private boolean isPrime(int num) {
        if(num==2)
        return true;
        // check if n is a multiple of 2
        if (num % 2 == 0 || num==1 )
            return false;
        // if not, then just check the odds
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0)
            return false;
        }
        return true;
    }
}

Sample input:

2
1 20
120 130

Sample output:

4
1

Constraints:

1 <= T <= 10000
1 <= A <= B <= 10^18

Answer 1

The maximum sum of squares-of-digits of an \$n\$-digit number is \$n\cdot9\cdot9 = n\cdot81\$. The number of digits in a number \$B\$ is \$\lceil\log_{10}(B)\rceil\$.

Since you only need to sieve to the square root of the number you're testing for primality, you only need to run your sieve from \$3\$ to \$\sqrt{\lceil \log_{10}(B)\rceil\cdot81}\$. Even for \$B\$ = 1 billion, this means the max you need to sieve to is \$28\$.

So, run the sieve once, and simply cache the results.

---

Also, if you wanted to be really cool, you could probably get some minor speed-ups by not calculating the sums-of-digits, and looping over them instead.

What I mean by that is this: notice that the sum of digits of \$32x\$ (where \$x\$ is any digit - read that as "three hundred and twenty-\$x\$") is always going to be \$3 + 2 + x\$, and the sum-of-squares will always be \$9 + 4 + x^2\$. Thus, instead of looping from \$320\$ to \$329\$ and calculating the sum-of-digits and sum-of-square-of-digits every time, you could just loop from \$x = 0\$ to \$x = 9\$, and check \$3+2+x\$ and \$9+4+x^2\$ for primality.

Using a bit of recursion, you could loop over all values of all digits.

Answer 2

I completely agree with @gabitzish.You can gain lot of performance improvement by storing all the primes up to some limit in array and access them in O(1). I would also suggest below techniques to improve the performance.

• If the number is divisible by 3 or 9 the the sum of digits also divisible by 3 or 9.You can skip many such number by a divisibility test by 3 or 9 and avoid very costly isSUM and isSUMsq calls.Also since you only need to test odd sums you can hop over the numbers once you found first odd sum. e.g. For range 120-130 sum of first number 120=1+2+0=3 so you can skip next number 121 since 1+2+1=4 and could not be a prime.The numbers like 11,101,110,100001 i.e. with 2 occurances of 1 can be easily identified with a simple test.
• You can improve the sum method by taking advantage of the fact that all the numbers you need to find the digit sum are in a sequence.

However all these improvements will improve the performance but it will be still not sufficient if n is very very large.With all the optimizations the time complexity would be still >>>>>>>>>n. Use of DP would be the best approach to solve this problem if you are really interested in O(n) or less.

Answer 3

You could use Eratosthenes sieve to find the prime numbers <= 1000 (or a proper value that can be the max sume of digits) before doing anything else, and not use isPrime function every time you need to check a number.

Answer 4

private boolean logic (long i) {
    if (isSUM (i) && isSUMsq (i)) {
        return true;
    } else {
        return false;
    }
}

This is a often to be seen pattern - the 'it is true if it's true, else if it's false it's false'-pattern.

Why don't you write:

private boolean logic (long i) {
    if ((isSUM (i) && isSUMsq (i)) == true) 
        return true;
    } else {
        return false;
    }
}

or

private boolean logic (long i) {
    if (((isSUM (i) && isSUMsq (i)) == true) == true) 
        return true;
    } else {
        return false;
    }
}

You may as well try to move into the opposite direction:

private boolean logic (long i) {
    boolean tf = (isSUM (i) && isSUMsq (i));
    return tf;
}

or just

private boolean logic (long i) {
    return (isSUM (i) && isSUMsq (i));
}

but probably, the compiler does the same for all those alternatives. Similarly, you have 2 places where you just may use:

return isPrime (sum);

But for performance reasons there are 3 other points much more relevant:

• get a faster prime checking algorithm. They are all over the place, so I don't repeat them here.
• If you perform multiple searches, caching the results should speed up things, depending on the numbers and the prediction you can make about these numbers.
• The build-in isProbablePrime should speed things up for really big numbers.

Answer 5

Additional performance improvements for isPrime:

• As others have said, you only need to test up to the square root of num, since every composite number has at least one prime factor less than or equal to its square root

• Additionally, cache known primes as you generate them and test subsequent numbers against only the numbers in this list (instead of every number below sqrt(num))

Answer 6

(So I wrote all this before I noticed your loop conditional used i * i <= num. I still think the below is valuable information, so I'll post it anyway. As far as whether it's cheaper to multiply each time or calculate a square root once at the beginning, it will probably depend on how big the numbers you're checking are.)

I agree with gabitzish that the best way to check for primes is using a sieve. However, a quicker improvement to your specific algorithm is to only check up to the square root of the number under question. Any checking above the square root, and you are simply checking for the factor pair of one of the smaller numbers you already checked.

For instance, 21 is not prime, because 3 * 7 = 21. Square-root of 21 is ~4.5826. By checking above that value, what I am really checking for is the 7 factor. But, I would have already found the 3 smaller 3 factor.

private boolean isPrime(int num) {
    if(num==2)
        return true;

    // check if n is a multiple of 2
    if (num % 2 == 0 || num==1 )
        return false;

    // if not, then just check the odds
    int limit = Math.sqrt(num); // Floor/truncation here is OK.
    for (int i = 3; i * i <= limit; i += 2) {
        if (num % i == 0)
            return false;
    }
    return true;
}

Answer 7

Instead of checking numbers, check the sets of digits in sorted order. Let's say you are looking for six digit solutions. Sum of squares of digits is at most 6 x 81, so you first create an array bool prime [6*81 + 1] and fill it. Then

for (a = 1; a <= 9; ++a)
  for (b = a; b <= 9; ++b)
    for (c = b; c <= 9; ++c)
      for (d = c; d <= 9; ++d)
        for (e = d; e <= 9; ++e)
          for (f = e; f <= 9; ++f)
            if (prime [a + b + c + d + e + f])
              if (prime [a*a + b*b + c*c + d*d + e*e + f*f)
                print all numbers made from the digits a,b,c,d,e,f. 

Even if you go up to 19 digit numbers, there are only about 1.5 million combinations of digits to check which should take only a few dozen milliseconds. Finding the numbers is then easy.

Even for 63 digit numbers, there are less than 10 billion combinations of digits to check.