# Find the 10001st prime number

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

• github.com/strikersps/Competitive-Programming/tree/master/… May 31 at 13:02
• The fastest method for getting the 10001st prime number is to store that prime number and just reply it. Practical applications which use prime numbers use pre calculated prime numbers from tables. Jun 30 at 20:08

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

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.