Ways to optimize your java code ?

[Abhinav Pande]

I want to optimize below code for efficient run time complexity.

The problem statement is: A number is called a "strange prime" if it is a prime number and its sum of digits (reduced to a single digit) is also a prime number. Sum of digits reduced to a single digit means that if the sum of digits have more than 1 digit, we again sum the digits and follow this process till we get a single digit. So if the number is 345181, then its sum of digits (reduced to a single digit) = 3+4+5+1+8+1 = 22 = 2+2 = 4.
Given a number n as input, return the value of the nth strange prime. Note that some strange primes are 2, 3, 5,7,11,23,29 and so on. 29 is a strange prime because it is a prime number and its sum of digits (reduced to a single digit) = 2+9 = 11 = 1+1 = 2 which is a prime number.
nthStrange(2) = 3
nthStrange(8) = 41

My Solution:

public class StrangePrimes {
  
 public static void main(String args[]) {
     
    StrangePrimes testInstance = new StrangePrimes();
    int result = testInstance.nthStrange(5);
    System.out.println(result);
 } 
 
 public int nthStrange(int num) {
     
     int j =0;
     int i = 3;

     if(num == 1) {
         return 2;
     }
     
     while(num!=1) {
     
     if(isPrime(i)) {

          j	= sumOfDigits(i);

	if(isPrime(j)) {
         
         num--;
         

     }

	

     }
                i++;
		i++;
        
     }
     
     return i-2;
     
 }
 
        public boolean isPrime(int n) {

               if(n%2 == 0) {
		 
		 return false;
		 }

		 int m = n/2;
            
             for(int i = 3; i<=m; i++) {
            
                if(n%i == 0)
                    return false;
                i++; 
            }

            return true;  
            
        }

 public int sumOfDigits(int k) {

	int sum = 0;

	while(k!=0) {

	sum += k%10;

	k = k/10;
}

   if(sum <= 9) {

	return sum;
}
	     
	return sumOfDigits(sum);
}

}

Note: Don't use arrays. Don't use built-in functions. Required a raw solution.

[Paul Clapham]

Welcome to the Ranch!

Abhinav Pande wrote:I want to optimize below code for efficient memory and run time complexity.

Efficient memory? I suppose that means you want to minimize the amount of memory used? Seems kind of pointless since the code creates only one object. And anyway it isn't any more efficient to use 1 kilobyte of memory than it is to use 100 kilobytes. Both numbers are trivially small compared to the amount of memory you have available.

And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

[Joanne Neal]

Abhinav Pande wrote:I want to optimize below code for efficient memory and run time complexity.

Before doing either of those, it's probably best to get some code that works.
Try calculating the 5th strange prime with your code.

[Abhinav Pande]

Joanne Neal wrote:
Before doing either of those, it's probably best to get some code that works.
Try calculating the 5th strange prime with your code.

code is correct now answer my question!

[Paul Clapham]

You need to answer mine first.

[Joanne Neal]

Abhinav Pande wrote:now answer my question!

Need working code first.
According to your latest code, the 6th strange prime is 13

[Charles D. Ward]

Abhinav Pande wrote:code is correct now answer my question!

Great way to ask for help.

[Abhinav Pande]

Joanne Neal wrote:
Need working code first.
According to your latest code, the 6th strange prime is 13

now its working! thanks for the review

[Abhinav Pande]

Paul Clapham wrote:

And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

http://en.wikipedia.org/wiki/Time_complexity

code written in such way that when it compiles should take less amount of time for program execution i.e. optimal solution
not a feasible one.

[Campbell Ritchie]

Abhinav Pande wrote: . . . code is correct now answer my question!

That is no way to talk to people who are trying to help. Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only. I think that merits an apology.

[fred rosenberger]

Abhinav Pande wrote:

Paul Clapham wrote:
And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

http://en.wikipedia.org/wiki/Time_complexity
code written in such way that when it compiles should take less amount of time for program execution i.e. optimal solution
not a feasible one.

Doing that is really more of an art, not a science. after all, it is possible the "optimal solution" hasn't been figured out yet.

Generally, when one is trying to optimize code, you start by defining requirements. and those should be SPECIFIC. there is almost always a way to make the code run faster, but the law of diminishing returns apply. is it worth it to spend 40 hours coding to save a microsecond? is it then worth it to spend 200 hours coding to save another? etc.

Also, at some point, it becomes cheaper to by bigger/faster hardware to get speed improvements than to improve the code.

Have you figured out what the complexity of your algorithm even is?

[Abhinav Pande]

Campbell Ritchie wrote:

Abhinav Pande wrote: . . . code is correct now answer my question!

That is no way to talk to people who are trying to help. Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only. I think that merits an apology.

I apologize, I didn't mean that actually but you are right

Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only.

It will never happen again. I'll choose my words correctly in the future.

[Paul Clapham]

If you want your code to run faster then basically there are two ways to do that: (1) Find the parts of your program which are executed most often and fix the code to execute them less often; (2) Write some different code which runs faster.

To use option (1) you should profile your code. To do that you need your code to run for some time, so finding "strange prime" number 6 isn't a good test. Finding number 6,000 would be better.

To use option (2) you need to do some mathematical thinking about the algorithm you chose (since it's a mathematical problem). For example you could write

public int sumOfDigits(int k) {
  return (k-1) % 9 + 1;
}

instead of what you had. I doubt this would speed up your code much, since your profiling wouldn't have pointed there as the most frequently-run code, but that's the sort of thing to do.

[Campbell Ritchie]

Apology accepted

[Abhinav Pande]

Campbell Ritchie wrote:Apology accepted

Thank you

[Campbell Ritchie]

Now, what algorithm were you using for finding primes, and for the sum of digits. The algorithm for finding primes looks as if it will run in quadratic time. There are far better ways to do that, for example the Sieve of Eratosthenes, which I suggest you read about.
Also, you do not need to loo as far as the number to find whether it is prime. Work out what the best value of the loop index m should be.