1
\$\begingroup\$

Project Euler 7: What is the 10 001st prime number?

I currently have this code:

let primesfound = 0;
for(i=0;i<Number.MAX_SAFE_INTEGER;i++){
  if(isPrime(i)){
    primesfound++
  }
  if(primesfound==10001){
    console.log(i)
    break;
  } else{
    console.log(i + `and ${primesfound} found`) //testing line
  }
}

but it's taking ages! There has to be a way to do it faster.

The isPrime() function:

  function isPrime(num){
  if(num<2){
    return false;
  }
  for(a=2;a<=num/2;a++){
    if(!(num%a)){
      return false;
    }
  }
  return true;
}
\$\endgroup\$
2
1
\$\begingroup\$

Testing every integer using trial division is probably the slowest way to find primes.

Change the algorithm to use one of the standard prime number sieves (e.g. Sieve of Eratosthenes).

\$\endgroup\$
1
\$\begingroup\$

I am not a javascript developer so most of this answer will focus on the algorithm rather than specific language usage.

There are some simple algorithmic improvements you can make without changing your entire algorithm. Firstly, there is a simple one - do you need to check every single number under n/2? Once you've checked if 2 is a divisor, there is no need to check if every following even number is a divisor. If 2 was a divisor, then you've already found out that n is not prime, and if 2 was not a divisor, then none of the even numbers will be divisors. To do this, I would add a simple edge case for n % 2 == 0 and n == 2, which would half the time taken.

Another improvement is that you don't need to check up to n / 2 - the highest number you need to check is sqrt(n), as sqrt(n)^2 == n. This will be a significant speedup for larger primes.

Another slightly more complicated speedup could be achieved by using the fact that all primes past 2 & 3 are of the form 6n ± 1 - so they're all either one above or one below a multiple of 6. To check primes this way, you can simply increase a by 6 each time, and then check if the numbers one below or one above a are factors of n. In terms of programming, it'd be easiest to start at 5, then check if a was a factor, or if a + 2 was. In pseudocode, the algorithm with all the above improvements might look something like:

# check edge cases first
if number is less than 2:
    return false
if number is 2 or 3:
    return true
if number is divisible by 2 or 3:
    return false

let upper_limit = integer_sqrt(num) + 1
for i from 5 to upper_limit in steps of 6:
    if (num is divisible by i) or (num is divisible by i + 2):
        return false
    
return true

This might not be enough to make it fast enough though, in which case using another algorithm would be the way to go.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.