CodeWars: Gap in Primes

Question

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 <= end; x++){
 if(x % 2 == 1){
 arr.push(x)
 }
 }
 for(var cache = arr.length, j = cache ; j >= 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
}

Answer 1

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 + 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 <= 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 <= 6) //cut away small primes explicitly
 return n === 2 || n === 3 || n === 5;
 //cut away small divisors (2 and 3) explicitly
 if (n & 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 <= 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)", "->", 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 :)

• Abdel-Raouf: Could you please comment your code.
• Oliver: @Abdel-Raouf, enjoy
• Abdel-Raouf: Why you used a bitwise operator "|", how could these improve the performance?
• Oliver: current = start | 1 is a replacement for whole if...else... statement. It runs in single CPU tick, doesn't use branching and doesn't use arithmetics.
• Oliver: Binary mask (you see, it's just a number) can filter bits from testing number only on positions where mask has. I'm interested only in the last bit, so I apply mask consisting only of this very bit. It appears to be just number 1. Why do I need only last bit? Because it essentially separates even and odd numbers.

Answer 2

You have a huge problem in your code! You are iteration from start to end and push every x % 2 == 1 into an array. Alone that takes a long time (with values between 3e6 to 4e6)!

So I wrote it completely new for you :)

function isPrim(x) {
	if (x === 2) return true; // as @Graipher commented
	if (x % 2 !== 0) {
		// you only need to check to the half of x
		for (var i = 2; i <= x / 2; i++) {
			if (x % i === 0) {
				return false;
			}
		}
		return true;
	}
	return false;
}
function gap(g, m, n) {
	var lastPrim = null; // cache-value
	// now the 'trick', check not every number to n
	// when you found the gap, you have it and then you can return with the result
	for (var i = m; i < n; i++) {
		if (isPrim(i)) {
			if (lastPrim === null) {
				lastPrim = i;
			} else if (i - lastPrim === g) {
				return [lastPrim, i];
			} else {
				lastPrim = i;
			}
		}
	}
	return null; // no result was found
}
console.log(gap(2, 0, 10)); // [1, 3]
console.log(gap(2, 2, 10)); // [3, 5]
console.log(gap(4, 0, 20)); // [7, 11]
console.log(gap(6, 100, 110)); // null
console.log(gap(8, 3e6, 4e6)); // [3000953, 3000961]

You can copy past it to codewars, it passes all tests

Edit: we found out that this solution is good and easy to understand, but when you have large gaps Oliver's improvements are taking part.

• Shinigami: @Graipher fixed, but it runs all tests on codewars. And also, this wasn't the problem of Abdel-Raouf
• Shinigami: @Abdel-Raouf 1-because if i found that x isn't prim, I can break out of the loop, 2-because it is cleaner and i check if lastPrim === null, I can also check if lastPrim === undefined
• Shinigami: I found a very interesting thing: 1-when I change my var's to let's it is ~0.5ms slower, 2-my solution is 1.5-1.8ms faster than Oliver's answer, but he uses so much 'improvements' | (everything tested in jsfiddle + gap(8, 3e6, 4e6) + console.time() and console.timeEnd() Chrome 55)
• Oliver: @Shinigami, try it on long run. Test with gap = 8 runs only over 500 numbers to find first match. Try gap = 120 to see the difference. And yes, let is usually slower than var
• Oliver: @Shinigami, see it yourself on jsfiddle. I didn't include test with 120 as it doesn't even complete