Abhinav Pande

Greenhorn

Posts: 9

posted 3 years ago

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:

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

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:

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

posted 3 years ago

Welcome to the Ranch!

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?

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

Rancher

Posts: 3742

16

Abhinav Pande

Greenhorn

Posts: 9

Joanne Neal

Rancher

Posts: 3742

16

Charles D. Ward

Ranch Hand

Posts: 99

1

Abhinav Pande

Greenhorn

Posts: 9

Abhinav Pande

Greenhorn

Posts: 9

posted 3 years ago

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.

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

Marshal

Posts: 56518

172

posted 3 years ago

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

Greenhorn

Posts: 9

posted 3 years ago

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

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

Campbell Ritchie wrote: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.Abhinav Pande wrote: . . . code is correct now answer my question!

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.

posted 3 years ago

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

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.

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

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.

Abhinav Pande

Greenhorn

Posts: 9

Campbell Ritchie

Marshal

Posts: 56518

172

posted 3 years ago

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.

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.