You can find isPrime in approximately every math package on every package registry. Most of them are great. A few of them are theatrical: 200 lines of code, two dependencies, and a BigInt path you will never reach. For inputs under a few million, you can write a clean, fast isPrime in eight lines and never think about it again.
This guide walks through the function step by step, with the reasoning behind each line, so you can drop it into a project, port it to whatever language you are using, and trust it for the inputs it is designed for.
Photo by betül nur akyürek on Pexels
What "small integers" means here
For this article, "small" means anything you can store in a regular signed 32-bit or 64-bit integer and divide without precision loss. In JavaScript, that is anything below Number.MAX_SAFE_INTEGER (2^53 - 1). In Python, the integer type is unbounded and the function still works, just slower for genuinely large inputs. In Go, C, Rust, or Java, anything that fits in int64 is fair game.
For huge primes (cryptographic sizes, hundreds of digits), you would switch to Miller-Rabin or AKS, both of which the Wikipedia article on primality tests covers well. We will not need them.
Step 1: handle the edge cases
The first three lines of the function are pure case-work.
function isPrime(n) {
if (n < 2) return false;
if (n < 4) return true;
if (n % 2 === 0) return false;
The order matters. By the time we have passed the third check, we know n is at least 3 and odd.
Edge-case bugs in primality functions are almost always in this block. Many implementations forget that 1 is not prime, that 2 and 3 are. A quick check the function gets right: isPrime(2) should be true, isPrime(1) should be false, and isPrime(0) should be false.
Step 2: knock out multiples of 3
if (n % 3 === 0) return false;
This catches another third of the remaining composites in a single step. The reason: after eliminating even numbers, the remaining candidates split into "multiples of 3" and "everything else." Multiples of 3 above 3 itself are composite, so we knock them out before getting to the loop.
This is a small optimization for small inputs, but it also enables the loop step pattern that follows. Without it, you would have to test 3, 5, 7, 9, 11, 13, ... and waste a check on every multiple of 3. With it, the loop can step in a pattern that skips multiples of both 2 and 3.
Step 3: the loop with the 6k +/- 1 pattern
for (let i = 5; i * i <= n; i += 6) {
if (n % i === 0) return false;
if (n % (i + 2) === 0) return false;
}
return true;
}
This is the only piece that takes any thinking.
The pattern i += 6, checking both i and i + 2 per iteration, walks through all numbers of the form 6k +/- 1: that is, 5, 7, 11, 13, 17, 19, 23, 25, 29, and so on. Every prime greater than 3 has that form, because anything else (6k, 6k +/- 2, 6k + 3) is divisible by 2 or 3, both of which we already eliminated.
The walk hits a few composites (25, 35, 49, 55), but that is fine. Trying a composite divisor that we have already implicitly tested against its prime factors does no harm; it just wastes an iteration. It is still much faster than testing every odd number.
The loop bound i * i <= n is the square-root cutoff. We test only up to the square root of n because every composite has a factor at or below it. (If n = a * b and both a and b were greater than the square root, their product would exceed n.) We use i * i <= n rather than i <= Math.sqrt(n) because integer multiplication is fast and avoids a floating-point conversion that could be off by one near the boundary.
For a derivation of the square-root ceiling and the small-prime list it produces, Wolfram MathWorld has the underlying number theory.
Photo by Magda Ehlers on Pexels
Tests you should write
Five test cases catch every bug this function tends to ship with.
isPrime(0) // false
isPrime(1) // false
isPrime(2) // true
isPrime(3) // true
isPrime(4) // false
isPrime(25) // false // catches the 6k +/- 1 walking past a composite
isPrime(169) // false // catches the loop missing 13 x 13
isPrime(101) // true
isPrime(997) // true // largest prime under 1000
If your implementation gets these right, you are in business for any input below Number.MAX_SAFE_INTEGER. The 25 and 169 cases are the ones that catch off-by-one errors in the loop pattern.
The Mozilla Developer Network has the canonical JavaScript reference if you need to double-check integer arithmetic behavior.
When to switch to a library
The honest answer is "not until you have to."
This function is good for inputs in the millions in any modern runtime. At a few billion, you start to feel the trial division. At ten billion, you want Miller-Rabin (probabilistic, fast, used by almost every cryptographic library) or a deterministic variant. At cryptographic sizes, you want a library, full stop.
But the threshold where "library or your own code" matters is far higher than most engineers assume. A library has a fixed cost: an import, a learning curve, sometimes a dependency. Your own eight-line function has zero. If you can write the tests and the inputs are bounded, the do-it-yourself path is cheaper and clearer.
For day-to-day checks at the desk (verifying a test fixture, sanity-checking a hash bucket size, settling an argument), this tool handles the same job in one click without any code at all. Its prime factorization output also tells you the factors when the answer is "not prime," which is something the function above does not give you.
A word on the math behind the speedup
Three optimizations sit inside the eight lines, and they compound.
The square-root cutoff drops the work from O(n) to O(sqrt(n)). For inputs near a billion, that is the difference between thirty thousand operations and a billion. It is the single biggest gain in the function.
Skipping multiples of 2 drops the work by half. Skipping multiples of 3 as well drops it by another third. The combined skip of multiples of 2 and 3 (the 6k +/- 1 pattern) leaves only a third of the candidates the naive loop would have tested.
Doing trial division with primes only would be even faster, but it would require carrying a prime table and a sieve. For the input range we are aiming at, the 6k +/- 1 walk is close enough and avoids the table. The trade-off is well known and described in the Project Euler forums and on the Numberphile site, both of which have practical examples of the trade-offs at different input sizes.
What this function does not do
It does not factor the number when the answer is "not prime." For that, you would extend it with a second loop that walks divisors and records hits. Most people who need both reach for a library at that point, because the factorization code starts to want shared utilities.
It also does not return any kind of certificate. Probabilistic primality tests in libraries return a "probably prime, with confidence X" answer. The function above is deterministic for its input range, so the binary answer is the right one. Just do not extend it to giant inputs and expect the determinism to come along.
For the full plain-language version of this method, with worked examples and the part about when to stop trying by hand, the companion blog article How to Tell If a Number Is Prime Quickly by Hand covers it. The procedure and the function are the same procedure, just expressed in different notations.
Closing the loop
You can paste the eight-line function into your project, add the test cases above, and stop thinking about primality testing for any reasonable input. If you find yourself reaching for it often enough that the desk-tool friction matters, the EvvyTools homepage has the same logic in a browser tab. Either way, the work goes from "specialized library question" to "noise in the background." That is the right place for it.
Top comments (0)