Checking If A Number Is Prime, Efficiently

If you've solved algorithm challenges on sites like Leetcode, HackerRank, or FreeCodeCamp, you've likely run into the need to check whether a number is prime or not. A prime number is any positive integer which is only divisible by itself and 1. In this post, I will highlight a common approach to this problem, and discuss how to improve its time complexity.

Accuracy

In proper JS fashion, there are multiple approaches that could lead us to an accurate solution. For instance, a brute-force approach could look something like this:

const num1 = 7;
const num2 = 4;

const isPrime = n => {
    if (n <= 1) return false;

    else if (n == 2) return true;

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

isPrime(num1);
// => true

isPrime(num2)
// => false

As you can see from the example above, we are able to write an accurate function with fairly simple logic:

1. If n is less than or equal to 1, return false.

2. Else if n is equal to 2, return true.

3. Else, loop through all numbers between n and 1 and return false if n is divisible by any.

4. When/if the loop ends, return true.

What is isPrime doing when called on num1? First, it checks if the argument is less than or equal to 1, because 2 is the smallest prime number. num1 has the value of 7, so it skips the if and if...else blocks. Next, in the else block, we loop through all the numbers between - but not including - our argument and 1. If our argument is divisible by any iteration of i, isPrime will return false. If our loop ends without a return, isPrime will return true. Because 7 is not divisible by any number between itself and 1, isPrime(num1) returns true. Try following the path of isPrime(num2) to find where it returns false.

Efficiency and Time Complexity

This function is perfectly accurate, but it is not as efficient as it could be. To highlight this, consider checking a large prime number such as 3779. That would require our function to perform 3777 tasks in the else block alone! In other words, the solution above has a time complexity of O(n), increasing linearly as the value of n increases.

We can improve our isPrime function's time complexity. Take a look at the following change:

const isPrime = n => {
    if (n <= 1) return false;

    else if (n ==2) return true;

    else {
        const maxDiv = Math.sqrt(n)
        for (let i = 2; i <= maxDiv; i++) {
            if (n % i == 0) return false;
        }
    return true;
    }
}

isPrime(3779);
// => true

isPrime(3778)
// => false

By only looping between 1 (exclusive) and the square root of n (inclusive), we are reducing the required tasks for isPrime(3779) from 3777 to 60. That's a big improvement. Now the time complexity of our solution is O(sqrt(n)), because the maximum number of required tasks is proportional to the square root of n.

Why It Works

But how is the maximum divisor of a number its square root? For example, 60 has many divisors, and some of them are definitely larger than its square root of 7.746. The important thing to note here, is that while 60 has divisors larger than 7.746 (10, 12, 15, 20, 30), each of them requires a factor smaller than 7.746 to reach the product of 60. In the for loop of our first solution, we are doing extra work by checking divisors twice, as well as many other unnecessary checks. Continuing with our example of 60, we don't need to loop through all the numbers between 1 and 60, because by the time we reach its square root, we have checked all the factor pairs. In other words, we checked all the larger divisors just by checking for divisors less than or equal to maxDiv.

Conclusion

There will always be many solutions to every algorithm problem, and not all solutions are created equal. Some require our machines to work much harder and longer than others, and understanding the time complexity of our solutions improves the efficiency of our code.

Depending on what kind of code you write, you will likely come across the need to check the primeness of a number. By applying what we know about prime numbers to our code, we can exploit their unique qualities to make our code cleaner and more efficient, without compromising accuracy. That's prime stuff.