Project Euler: Problem 7- 10001st prime (code inefficiency)

https://learn.freecodecamp.org/coding-interview-prep/project-euler/problem-7-10001st-prime

For this problem, my code won’t pass the last test due to inefficiency but having a hard time finding ways to improve it. As you see in my code, I’m not looping through all the numbers as I start at the square root of each number being analyzed.

function nthPrime(n) {
  let count = 0;
  let prime;
  let j;
  let i = 2;

  while (count < n) {
    for (j = Math.ceil( Math.sqrt(i) ) ; j > 1; j--) {
      if (i !== j && i % j == 0) break;
    }
    if (j == 1) {
      count++;
      prime = i;
    }
    i++;
  }
  return prime;
}

nthPrime(10001);

Hi, it seems that you are testing every number, starting with 2 (variable i). A first approach could be start with i=3 and increment variable i by 2 (3,5,7…) so you can test all odd numbers (even numbers are NOT prime, so…why test them?). Notice that you are starting with prime #2 ( 3 is the second prime). Take it into account.

A deeper approach is possible if you generate on-the-go an array with each prime number detected, so, if you test forward (from 3 to sqrt(n), against that array, you will dramatically reduce the amount of tests. I mean the variable j could come from that array. The array will grow every time you find a new prime.

Some ideas, hope they may be useful.
Regards, Esteban

1 Like

Hey Estaban- thanks for the time to help.

I implemented the first part of your suggestion in not testing even numbers, but still not efficient to pass the last test.
I’m not understanding what you’re doing in the second suggestion. I’m finding prime numbers starting from 3, and for each find I track how many I found with the variable “counter”. Also, 2 is the only even number that is prime as I confirmed thru google. I’m not sure why you want to create an array listing out the prime’s when I track mine with “counter”. How is yours shortening the tests and which part of the test are you shortening- the area where you test if a number is prime? I see this part as very calculation heavy.

to find if it is prime you are testing a number against all other numbers that are lower than the square root of it. To make it more efficient cound’t you test the number only against primes lower than the square root of it?

Hi ! the most efficient way to test if a number n is prime would be to check that none of the first prime numbers, from 2 to sqrt(n) is a divisor. the answer from http://forum.freecodecamp.org/u/Ieahleen is correct.

Let’s suppose that you are testing if number 10001 is prime.
The square root limit is 100.

Your first solution was to check every divisor number. (about 100 numbers)
Your 2nd solution was to check only odd divisor numbers (about 50 numbers).

BUT,there are 25 prime numbers from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
So, if you manage to use them, only 25 divisor tests will do it.

When I said “keep track” I meant to store each prime number you are finding in an array and use that array to test if n is prime. not just count them. You must also count them to express a valid solution to the problem.

Hope this could clarify. Regards, Esteban

@leahleen I didn’t know that was possible to only test prime numbers below the number you are testing to see if it’s a prime. Is this a math rule?

Well, consider this…

Is 155 a prime?

The square root is 12.4

So, what are the numbers to check?

13 - this is a prime
12 - this is 4x3, you can just check if 155 is multiple of 3 or 2
11 - prime
10 - 5x2, you can just check 5 and 2
9 - 3x3
8 - 2x2x2
7 - prime
6 - 3x2
4 - 2x2
3 - prime
2 - prime

If you just check 13, 11, 7, 5, 3, 2 there is less work

You can do this by having the array of primes, and check against 155 from the smaller in the array (2), to Math.ceil(Math.sqrt(155))

If you do this for each number there is manny less comparisons to do, and so less resources needed

Gotcha. I see what I need to implement now. Funny thing is that FreeCodeCamp’s solution doesn’t pass on the last test? :confused:

@Esteban- thanks! I know what I don’t know now.

I implemented this approach. However, while testing the code in editor provided in FCC, it does not print the output for number beyond 800. It gives the error message “Potential infinite loop detected on line xx. Tests may fail if this is not changed.”. When I run all tests, it passes even for last case to print 10001th prime. I removed all console.log messages and tried. It gives the same infinite loop error message. Is there anything I should avoid or do to get rid of this potential infinite loop message and run the code in the FCC javascript editor?

remove all unnecessary things, like the console.log statements, that occupy resources

try to optimise the code as much as possible
after a certain time of execution the tests time out and fail - you need to make your code more efficient

1 Like