Optimizing Javascript code for finding prime numbers

Question

I'm attempting a codewars.com challenge and I'm having some issues with making my code more efficient. The instructions for the challenge are to find all the primes in a range, then I have to find two prime numbers with a specified gap between them.

I've written an algorithm that works but takes too long to complete all of the test cases. You can see the code below:

function gap(g, m, n) {
// your code

var stopNumber;
var checkIfInteger;
var primeNumbersInRange = [];
var arrayIndex = 0;
var gap;

//iterate through all of the numbers in the range and find if they're prime
for( var numberToCheck  = m; numberToCheck <= n; numberToCheck++){

      var checkedTwoAndThreePass = true;

      checkIfInteger = numberToCheck / 2;

      if(Number.isInteger(checkIfInteger)){
        checkedTwoAndThreePass = false;
      }

      checkIfInteger = numberToCheck / 3;

      if(Number.isInteger(checkIfInteger)){
        checkedTwoAndThreePass = false;
      }

      if(checkedTwoAndThreePass){

        var k = 1;
        var primeNumberCheck = true;

        stopNumber = Math.sqrt(numberToCheck);

        while( ((6 * k) - 1) <= stopNumber & primeNumberCheck === true ){

          checkIfInteger = numberToCheck / ((6 * k) - 1);

          if(Number.isInteger(checkIfInteger)){
            primeNumberCheck = false;
          }      
          else{

            checkIfInteger = numberToCheck / ((6 * k) + 1);

            if(Number.isInteger(checkIfInteger)){
              primeNumberCheck = false;
            }
          }
          k++;
        }

        if(primeNumberCheck === true){
          primeNumbersInRange[arrayIndex] = numberToCheck;
          arrayIndex++;
        }

      }  

}

for(var i = 0; i < primeNumbersInRange.length; i++){
  gap = primeNumbersInRange[(i+1)] - primeNumbersInRange[i];
  if(gap === g){
    var primeNumbersThatMeetGap = [primeNumbersInRange[i], primeNumbersInRange[(i+1)]];
    return primeNumbersThatMeetGap;
  }
} 
var primeNumbersThatMeetGap = null;
return primeNumbersThatMeetGap;
}

What are the constraints for this problem (how large can the bounds of the range be)? — kraskevich, Jan 08 '17 at 20:36
A basic https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes can avoid many duplicate checks. Since "all" the primes need to be found.. — user2864740, Jan 08 '17 at 20:37
Can you decide on an indentation style and clean up your code accordingly? Also, you have an `&` where you probably want an `&&`. Check your code on jshint.com and fix all errors. — Tomalak, Jan 08 '17 at 20:39
Is this the kata? https://www.codewars.com/kata/gap-in-primes/javascript — BrunoLM, Jan 08 '17 at 20:41
take a look at related [Prime numbers by Eratosthenes quicker sequential than concurrently?](http://stackoverflow.com/a/22477240/2521214) — Spektre, Jan 09 '17 at 08:27

score 0 · Answer 1 · edited May 23 '17 at 11:52

0

One possible way is to implement Sieve of Eratosthenes algorithm. Example implementation here.

But that alone is not going to be enough. You will need to find a way to not repeat yourself all the time or go search only what is needed for the problem.

edited May 23 '17 at 11:52

Community

1
1

answered Jan 08 '17 at 21:34

BrunoLM

97,872
84
296
452

I did solve it with my first hint here, but the second hint makes everything so much simpler. – BrunoLM Jan 08 '17 at 21:35

score 0 · Answer 2 · edited May 23 '17 at 11:52

I have implemented this job by utilizing the Sieve of Sundaram which is normally believed to be slower than the Sieve of Eratosthenes however with a little optimization it has turned out to be around 2 times faster than the fastest implementation of the Sieve of Eratosthenes implemented under that question. Finding the 78498 primes in first 1M numbers took less than 25ms.

You can see it working in this answer.

Currently i am working on a segmented version of this algorithm which would yield;

a much faster response on the order 10^9 with single core.
bigger jobs to be spawned over the available free threads by using workers.

Once i finalize the code i will enlist it as a supplement under my existing answer in that topic.

Optimizing Javascript code for finding prime numbers

2 Answers2