Puzzle: 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 < 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
``````
-

The maximum sum of squares-of-digits of an `n`-digit number is `n*9*9` = `n*81`. The number of digits in a number `B` is ⌈log10(B)⌉.

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(⌈log10(B)⌉*81). 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 + x2. 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*x` for primality.

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

-
i didnt understand how @3+2+x can be generalized if i need to loop b/w 100-300 etc., –  cypronmaya Jan 29 '12 at 18:40

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.

-

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)`)

-

(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;
}
``````
-
``````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.
-