Checking Whether a Number Is Prime

In this lesson you'll learn an algorithm for checking whether a given number is prime, so you can understand an efficient checking method. This is for people searching "JavaScript prime number check" or "prime number algorithm."

Whether a number is prime (divisible only by 1 and itself) can be determined by checking whether it's divisible by any number from 2 up to "the square root of that number." If none of them divide it evenly, it's prime. The key insight is that cutting the check off at the square root, rather than testing every single number one by one, dramatically reduces the amount of computation.

The sample code effectively loops only through the range "up to the square root" by using the condition i * i <= n. Writing it this way, instead of using Math.sqrt(), is a slightly clever algorithm that also skips the computational cost of the square root itself. Try comparing the results for two numbers, 17 and 18.

A common beginner stumbling block is the reasoning behind why you only need to check up to the square root. Any pair of numbers that divides a given number evenly must have one member at or below the square root and the other at or above it, so it's sufficient to only check the range at or below the square root — a property this algorithm relies on. Thinking through how to check something efficiently is great practice for learning the fundamentals of algorithms.

This is an important mathematical property that's also used at the foundation of cryptographic technology, and devising an efficient checking algorithm is one of the basics of computer science. Encryption technologies like RSA, which secure internet communication, rely on calculations involving large prime numbers as their core technique.