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 = 0; j--){
  for(var i = 2; i <= 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 & 1) { //is it odd?
if (start > 2 || end ", gap(8,3000000,4000000)); // ~5ms
console.log("gap(120,3000000,4000000)", "->", gap(120,3000000,4000000)); // ~600ms



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

StackExchange Code Review Q#153288, answer score: 4