What type of improvements should be done for efficiency?

JavaScript
1

What should be done for the code efficieny? I could not passed at this section of the Euler project. The following code is the answer of: “What is the n th prime number?”, please explain it to me the improvements. Thanks.

function nthPrime(num) {
   let step = 0;
   let dv = 2;

   while (step < num) {
      let counter = 0;
      for (let ds = 1; ds <= dv; ds++) {
         dv % ds === 0 ? counter++ : counter;
      }
      if (counter === 2) {
         dv++;
         step++;
      } else {
         dv++;
      }
   }

   return dv - 1;
}

console.log(nthPrime(6));
1 Like
2

Do you have a link to the challenge? I couldn’t find anything by that title in the Euler Project list.

3

You will want to take a step back and write out the objectives in plain language and then translate that into code because your current solution will not produce what you need, unfortunately.

It looks something like this:

I want to find the nth prime number in the primary sequence of numbers.

I know that I can skip any even number except for 2 as it is the first prime number.

I know that when I’m testing numbers I should start at 2 and work up since every number is divisible by 1.

I want to make sure that once I’m working on checking a specific number to see if it is prime, I want to make sure it is not divisible by any number that came before it. As soon as it is divisible, immediately continue on to the next number in the sequence of numbers.

Every time I find a prime number, I will increase a counter that tells me what nth number I’m on and keep working until that counter matches the nth number. Once the counter matches the nth number, I will return the last prime that was found and consider the function done.

Then, all you have to do is translate what you write down into code, piece by piece. Writing out your code like this is a great practice because you can outline the logic of what you want to do in your spoken language and then translate each section into code!

1 Like
4

Hello!
The challenge is 7th problem in Project Euler folder, challenge’s name is ‘10001st prime’. The link is this.

As @marcusparsons indicated, I wanted to code functions as described below.

I want to find the nth prime number in the primary sequence of numbers.

I know that I can skip any even number except for 2 as it is the first prime number.

I know that when I’m testing numbers I should start at 2 and work up since every number is divisible by 1.

I want to make sure that once I’m working on checking a specific number to see if it is prime, I want to make sure it is not divisible by any number that came before it. As soon as it is divisible, immediately continue on to the next number in the sequence of numbers.

Every time I find a prime number, I will increase a counter that tells me what nth number I’m on and keep working until that counter matches the nth number. Once the counter matches the nth number, I will return the last prime that was found and consider the function done.

If you have an idea for any improvements for the code, please let me know :slight_smile:

5

Thank you @marcusparsons for your nice and detailed explanation. I will definitely pay attention to writing code in that way! :slight_smile:

1 Like
6

Thanks for letting us know which test, it allowed me to put in your code and test it.

I see your code actually works when put into the problem, although I found it a little confusing to work my brain through :). Problem is that it just can’t pass the last test of 10001 because it times out. So yes, definitely need to increase the efficiency.

One thing to note about testing to see if a number is a prime, you don’t need to check every number below the desired number to see if it divides. For instance, lets find out if 15 is prime.

We can start at 2 because every number is divisible by 1 (although you compensate for that by checking to verify if your counter is 2 ).

2 * nothing = 15
3 * 5 = 15
4 * nothing = 15
5 * 3 = 15

we could continue but there are no others.

If you notice, we did unnecessary work. We spend the time to check if 3 was divisible, but then we also checked 5… but based on previous test of 3, we already knew 5 divided. Can you figure it out from there?

If not: SPOILER ALERT:

Basically, when checking to see if a number is prime, you only need to check up to and including the square root of the number your searching because past its sqrt any number that divides with it would have already been checked by a number below the sqrt.

This doesn’t matter for a smaller number, but lets say for 100, instead of checking 99 numbers to see if any divide, we only really need to check up to 10 (the sqrt) because

2 * 50 = 100   ( basically meaning 100 % 2 = 0 )
4 * 25 = 100     ( basically meaning 100 % 4 = 0 )
5 * 20 = 100   ( basically meaning 100 % 5 = 0 )
10 * 10 = 100   ( basically meaning 100 % 10 = 0 )
20 * 5 = 100   ( basically meaning 100 % 20 = 0 )
25 * 4 = 100    ( basically meaning 100 % 25= 0 )
50 * 2 = 100   ( basically meaning 100 % 50 = 0 )

so anything past 10 was just repeating work. As you get into the thousands this saves TONS of time.

I rewrote your code with this in mind and it does pass… won’t spoil anything further by giving specifics :slight_smile:

7

Also, I didn’t want to overlook the two efficiencies mentioned in Marcus’ structuring.

First, you don’t need to check even numbers, because there are no even prime numbers aside from 2. So at dv=3 you could dv+=2 instead of dv++ which would check only odd numbers, but would need some additional logic to handle 2, and the second point below would make this first point not matter much.

Second, once you find a divisor, you can stop looking as you know its not prime. So typically once you find a divisor, you would break out of the for loop and conclude it isn’t prime and move on instead of continuing to check for divisors. This would eliminate the need for point 1 as the first divisor you would check is 2, and then would break the loop. One problem with this thought and your code is that you’re utilizing the counter to indicate if you found a prime or not, and if you break the loop when finding a divisor the counter would always equal 1. Your code would need maybe a boolean or something.

Lastly, and this isn’t really an efficiency thing, more just a repetitive thing:

This:

      if (counter === 2) {
         dv++;
         step++;
      } else {
         dv++;
      }

Would do the same thing as this:

      if (counter === 2) {
         step++;
      } 
      dv++;

but I think the second is more readable.

8

Wow, that explains a lot! Thank you @kinome79 !