Sum of the digits is prime or not 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 &lt; 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 &lt;= m; i++) {
            if (logic(i)) {
                count++;
            }
        }
        return count;
    }

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

    private boolean isSUMsq(long i) {
        int sum = 0;
        while (i &gt; 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 &gt; 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 &lt;= num; i += 2) {
            if (num % i == 0)
            return false;
        }
        return true;
    }
}


Sample input:

2
1 20
120 130


Sample output:

4
1


Constraints:

1 &lt;= T &lt;= 10000
1 &lt;= A &lt;= B &lt;= 10^18
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.