[JAVASCRIPT] How to find Prime Numbers. Fast.

There is only one thing that I love more than algorithms: Improving algorithms! This article will not explain one of those sophisticated formulas — but it will hopefully show you, how thoughtful thinking and tinkering will help you with optimising your code.

Nota bene: Think Python is fasteer? Try it!

What’s a prime number? All of you know that: It’s a number with only two divider natural divisors: 1 and the number itself.

And when you ask someone for a prime number algorithm, you get two answers: A mathematican will throw out a complex formula, like Mill’s formula:

Wait, what? Ok. The other answer is just a simple loop that checks if there is another number, lower than the number in question, where the operation modulo returns 0. The so called “trial division”. In other words: The number in question divided by the other number returns a third number and all numbers are natural, not factorized.

function isPrime(number) {
    for (let i = 2; i < number; i++) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

Let’s run this loop to find primes up to 50.000:

let startTime = performance.now();

let count = 0;

for (let number = 2; number < 50000; number++) {
    if (isPrime(number)) {
        count++;
    }
}

let endTime = performance.now();
let executionTime = endTime - startTime;

console.log(`found ${count} primes`);
console.log(`Execution time: ${executionTime} milliseconds`);

Did you know? You can run JavaScript inside Visual Studio Code. Just hit Ctrl+F5. Don’t know where to click. I’m a shortcut-nerd.

On my machine this will take 212 milliseconds and find 5.133 primes (your results may differ on a different machine):

Wait a minute! JavaScript is dozens of time faster than… Python?

Jepp. Let’s see if we could add another level of disgrace:

Let’s start with some obvious things: We don’t need to test all numbers in our “test division”. In fact we can skip every divisor lower than “number / 2”. Why is that? Because if the divisor is greater than “number / 2” the result must be lower than 2 and a faction.

function isPrime2(number) {
    let limit = Math.floor(number / 2);
    for (let i = 2; i <= limit; i++) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

let startTime = performance.now();

let count = 0;

for (let number = 2; number < 50000; number++) {
    if (isPrime2(number)) {
        count++;
    }
}

let endTime = performance.now();
let executionTime = endTime - startTime;

console.log(`found ${count} primes`);
console.log(`Execution time: ${executionTime} milliseconds`);

Again, similar to the Python solution, this halves the calculation time to, but not to 100 milliseconds

But there’s even more in this limit declaration: We can reduce it to the square root (sqrt) of our target number. Because if one divisor is greater than sqrt(number) the other divisor must be lower than sqrt(divisor). Meaning: They have already been checked. Let’s do it:

function isPrime3(number) {
    let limit = Math.floor(Math.sqrt(number));
    for (let i = 2; i <= limit; i++) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

let startTime = performance.now();

let count = 0;

for (let number = 2; number < 50000; number++) {
    if (isPrime3(number)) {
        count++;
    }
}

let endTime = performance.now();
let executionTime = endTime - startTime;

console.log(`found ${count} primes`);
console.log(`Execution time: ${executionTime} milliseconds`);

WHAT THE ACTUAL HECK-IDDI-HECK! 4 Milliseconds? Remember Python and 72 Milliseconds?

What’s next?

Why do we check even numbers at all? It’s “natural law” that an even number cannot be a prime (except the magic number 2).

We can safely skip them in our main loop. But not only there, we can also safely skip them in the “test division”. An even factor always leads to an even product in a multiplication. This leads to the assumption, that an even number always leads to a modulo unequal 0 when thrown against a prime!

In JavaScript it is a little trickier to check for the last digit of a number (aka last char of a string).

function isPrime4(number) {
    let limit = Math.floor(Math.sqrt(number));
    for (let i = 2; i <= limit; i++) {
        if ([0, 2, 4, 5, 6, 8].includes(parseInt(i.toString().slice(-1)))) {
            continue;
        }

        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

Let’s add this logic to both loops:

let startTime = performance.now();

let count = 0;

for (let number = 2; number < 50000; number++) {
    if ([0, 2, 4, 5, 6, 8].includes(parseInt(number.toString().slice(-1)))) {
        continue;
    }

    if (isPrime4(number)) {
        count++;
    }
}

let endTime = performance.now();
let executionTime = endTime - startTime;

console.log(`found ${count} primes`);
console.log(`Execution time: ${executionTime} milliseconds`);

Remember Python? This “silly” approach took a lot time. Same in JavaScript, it increases running time to 47 Milliseconds:

Again — We should implement the last test a little smarter. Right now we are using some string operations and apparently they are slow as heck.

Python allows us to change the step rate of the range() function. This way we could just skip even numbers in the loop itself. Way easier. Heads up: As we will start at 3 now, we increment the counter integer beforehand:

function isPrime5(number) {
    let limit = Math.floor(Math.sqrt(number));
    for (let i = 3; i <= limit; i += 2) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}


let startTime = performance.now();

let count = 1;

for (let number = 3; number < 50000; number += 2) {
    if (isPrime5(number)) {
        count++;
    }
}

let endTime = performance.now();
let executionTime = endTime - startTime;

console.log(`found ${count} primes`);
console.log(`Execution time: ${executionTime} milliseconds`);

It’s not way faster than our initial approach, but it still beats Python by lengths.

Now, as JavaScript is this fast, let’s increase the numbers a little and see how the improved algorithm performs against Python: How long does it take to find all primes up to… wait for it… it’s gonna be legendary… 100 Million!

This is JavaScript performance:

And this is Python:

I stopped the script after 10 Minutes. Check the other post to find out how to improve Python even more!

According to https://t5k.org/howmany.html we have 5.761.455 prime numbers lower than 100.000.000.

Update — What about Rust and C++?

The story does not end here. I tried the same algorithm with Rust. Implementing a progress bar here led to a desaster, I stopped the search after 5 minutes. Without the progress bar it took 400 seconds. A lot of room for improvement.

And even C++ surprised me in the beginning. The first run took 70 seconds, that’s almost twice the time JavaScript needed. Why that? After a little research I found out, that -O3 and -ffast-math arguments for the compiler are recommended. Now the algorithm is done after 40 seconds:

So… JavaScript is as fast as C++, when it comes to simple calculations. Disclaimer: I’m not a C++ or Rust developer. Leave a comment, if you can explain this!