Help me to speed up my function

JavaScript
1

So, I’m working on https://learn.freecodecamp.org/coding-interview-prep/project-euler/problem-7-10001st-prime where for given parameter n I need to return n-th prime number. My code works, but it’s not fast enough. Any suggestions?

function isPrimeNumber(number) {
  for (let i = 2; i < number; i++) {
    if (number % i == 0) return false;
  }
  return true;
}

function nthPrime(number) {
  let counter = number - 1;
  let currentNumber = 1;
  
  if (number == 2) return counter;

  while (counter) {
    currentNumber += 2;
    if (isPrimeNumber(currentNumber)) counter--;
  }
  return currentNumber;
}
2

The method you’re using here is woefully inefficient, for a few reasons

You’re testing every number if it’s divisible by every number below it, which is wasteful effort

You only need to try prime factorise it with all primes found so far. Recall that every number can be expressed as a product of prime factors. If you prime factor a number with all primes smaller than it, what remains is either 1 or another prime to add to the list

Having said that, it’s probably worth investing in a prime number generator. You’ll have to do a bit of research as to which to consider (the sieve of Eratosthenes needs too large a space without certain nontrivial modifications in js, trivial in Haskell)

Edit: I phrased this incorrectly, I didn’t mean that you need to actually do the prime factorisation, just that the only numbers you need to check divisibility of are the prior primes

1 Like
3

Yeah, your suggestion was helpful and my current solution is way faster… for param = 1000 it takes only 20ms(with previous solution it took about 160ms) and for param = 10001 it takes about 1958 ms(previously it took about 20000ms)… But it’s still not enough for tests to pass…
here is my current solution…

function nthPrime(number) {
  let counter = number - 1;
  let currentNumber = 1;
  const primeNumbers = [2];
  if (number == 2) return currentNumber;

  while (counter) {
    currentNumber += 2;
    let flag = true;
    
    for(let i = 0, count = primeNumbers.length; i < count; i++) {
      if(currentNumber % primeNumbers[i] == 0) {
        flag = false;
        break;
      }
    }

    if (flag) {
      counter -= 1;
      primeNumbers.push(currentNumber);
    }
  }
  return currentNumber;
}

I don’t like the fact I’m using flag. I need to figure out something else…

4

This is a great example of why big O notation is important. So many chances to add inneficiencies. You keep having to check the same numbers.

I think the best bet is to implement a sieve of Eratosthenes. That is usually the most efficient way to find prime numbers.

5

I see your point… I’ll try to improve the solution with these new insights on mind…