CodeWars: Gap in Primes I wrote JavaScript code for finding the first two consecutive prime numbers (that doesn't have divisors except one and itself) with a specific gap between them. It works well but take too much time to give results for large numbers.

When I tested this, it took about 48s to give the result:


  gap = 8 ,start = 3,000,000 and end = 4,000,000


I read about how to cache to minimize access for properties as length and put variables in local scope to make the code more efficient, but it didn't help me a lot. I then tried to optimize the for loops, but it affects the functionality of the code.

Link to challenge

function gap(gap, start, end){
 var arr = [];
 var counter = [];
 var result;
 for(var x = start; x &lt;= end; x++){
  if(x % 2 == 1){
   arr.push(x)
  }
 }
 for(var cache = arr.length, j = cache ; j &gt;= 0; j--){
  for(var i = 2; i &lt;= Math.sqrt(arr[j]); i++){
   if(arr[j] % i === 0){
    if(i != arr[j]/i || i * i == arr[j]){
      counter.push(arr[j] / i)
      arr.splice(j, 1)
      break;
    }
   }
  }

  if((arr[j+1] - arr[j]) == gap){
   result = [arr[j], arr[j+1]]
  }else if (result == undefined){
   result = null
  }
 }

 return result
}
In order of significance for performance


Don't use array to store prime numbers. You only need one previous
prime to remember. And even if you ever do this, don't remove
elements from its middle, as shifting array contents is very costly.
Store number from expensive Math.sqrt(), don't re-calculate it every iteration. Basically, this is rule for every loop - precalculate limits if possible.
There is only one even prime number: 2. It gives you great opportunities to quickly remove some edge cases:
If gap is odd, only 2 can be a first number. This condition is worth checking at the very start of your function
If number is greater than 2, it can be prime only if it is odd. This allows you to skip half of testing numbers by increasing counter by 2 each iteration, not just ++
Prime testing can be further improved by using 6k ± 1 pattern. It saves you one extra check every 3 odd numbers
You are testing prime numbers in loop. Create a function for this, isPrime or something




function gap(gap, start, end) {
  //cut off odd gaps
  //bitwise AND can test least significant bit
  //odd numbers have 1, even have 0
  if (gap &amp; 1) { //is it odd?
    if (start &gt; 2 || end &lt; gap + 2) return null; //check if 2 is in range
    return isPrime(gap + 2) ? [2, gap + 2] : null; //check additionally the other part
  }
  var previous = null; //no initial value
  //loop over odd numbers to check for primes
  for (var current = start | 1; //set last bit to 1: /odd numbers stay same, even numbers become next odd
       current &lt;= end;
       current += 2 // skip any even number
      ) {
    if (isPrime(current)) {
      if (current - previous === gap) //is it a match?
        return [previous, current];
      //no need for "else" here as the other branch has "return"
      previous = current; // anyway, save it
    }
  }

  return null; //no early return from loop = nothing matches

  
  /**
    Tests if n is prime
  */
  function isPrime(n) {
    if (n &lt;= 6) //cut away small primes explicitly
      return n === 2 || n === 3 || n === 5;
    //cut away small divisors (2 and 3) explicitly
    if (n &amp; 1 === 0 || //using bitwise AND for even numbers
        n % 3 === 0) return false;
    
    var limit = Math.floor(Math.sqrt(n)); //precalculate loop limit
    // loop is checking every divisor using 6k ± 1 pattern
    for (var t = 5; //start with 5, first 6k - 1 number
         t &lt;= limit;
         t += 6 //step by 6
        ) {
      if (n % t === 0 || //6k - 1
          n % (t + 2) === 0) //6k + 1
        return false;
    }
    return true;
  }
}
console.log(""); //this makes console output timestamp
console.log("gap(8,3000000,4000000)", "-&gt;", gap(8,3000000,4000000)); // ~5ms
console.log("gap(120,3000000,4000000)", "-&gt;", gap(120,3000000,4000000)); // ~600ms




Working fiddle. I submitted it on CodeWars, it passes :)