Check Prime Number in JS? O√n Complexity!

Checking whether a number is prime or not is a good example of algorithms that can be improved. Below is the solution with O√n time complexity to check for prime number in JavaScript!

function checkPrimeNumber(x) {
    if (x <= 1) return false;

    for (let i = 2; i < Math.sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}

Read more for detailed explanations!

What is a Prime Number?

Before we design an algorithm, we need to first understand the problem. In this case, what is a prime number?

A prime number is a whole number greater than one that is consisted of the number 1 and the number itself as its only factors. Factors are numbers that if multiplied, will result to a certain number. For example, 1, 2 and 4 are factors of 4. You see, 1 times 4 equals 4 and 2 multiplied by 2 results to 4.

If you need more explanations on prime number, you can read this helpful article!

How to Check Prime Number in JavaScript? Explained

Okay, you’ve read the code, but now you want more explanations. Here you go!

Firstly, we have to think about what makes a prime number. A prime number is greater than 1, so we exclude 1 by returning false. Since 0 and negative numbers can’t be prime, we’ll exclude those as well with this code.

if (x <= 1) return false;

Next, prime number can only be divided by 1 and the number itself. So, we have to test if it is dividable by any other number, if it could, then it’s not a prime number and we’ll return false. Then, how do we test it?

We’ll loop through every number from 2 to the number before itself and divide the number being tested with the current number in the loop.

For example, the number being tested is 51, we loop from 2 to 50 and try to divide 51 by each number from 2 to 50.

In the case of number 2 being tested, since the test starts from 2 until one number before the number being tested, 2 doesn’t get tested and skips directly to the next part.

The test is implemented with this code. Do notice that it is looped until x instead of Math.square(x) which will be explained later. Do notice that it is looped until x instead of Math.sqrt(x) which will be explained later.

for (let i = 2; i < x; i++) {
    if (x % i == 0) {
        return false;
    }
}

Those codes above will filter out the non-prime numbers. If the number passes those tests, then it is indeed a primber number and we’ll return true to signal that it is a prime number with this code.

return true;

Those codes above combined will result to :

function checkPrimeNumber(x) {
    if (x <= 1) return false;

    for (let i = 2; i < x; i++) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}

There we have a working solution with O(n) time complexity since we loop through 2 to n.

Improving to O√n Complexity

You’ve guessed it, we can improve the complexity by change the loop. We previously loop to x, now we loop to √x or in JavaScript, Math.sqrt(x).

This is the final code with O√n time complexity, which is the same as the first answer you’ve seen.

function checkPrimeNumber(x) {
    if (x <= 1) return false;

    for (let i = 2; i < Math.sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}

How does changing the loop count affects the code? Is it still accurate?

You actually only need to test the number until the square root of the number itself and yes it is accurate.

Let’s take 16 as example. Its factors are 1, 2, 4, 8 and 16.

As you can see, 1 * 16 = 16, 2 * 8 = 16, 4 * 4 = 16. There’s no need to test after the number 4 which is the square root of 16 since we’ve already found all the possible factors. That’s why we only need to test until √x.

Summary

Now we’ve learnt how to check for prime numbers in JavaScript and even improve it to O√n time complexity.

These small tweaks can greatly improve an algorithm’s time. We really have to understand the problem then we can solve and even improve it. That’s how important algorithms are.

If you are interested on another topic about algorithms in JavaScript, check out How To Flatten An Object With Recursion In JavaScript.

For you who want to brush up your JavaScript skills, whether to deepen or learn form zero, I recommend you try Codecademy. There are tons of JavaScript lessons that you can learn in a structured and interactive way. You can learn from the most basic materials to advanced stuffs and even preparing for technical interviews. Go try it now!

If you have a better solution be it code-wise or efficiency-wise, please do comment below!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript!

See you next post!