Most engineering writeups about primality testing dive straight into Miller-Rabin or AKS. That is fair when the input is hundreds of digits long. For the inputs you actually meet in a Tuesday-afternoon bug report, where someone is sending you a four-digit transaction ID and you want a quick sanity check, you can do the work in your head. No library, no shell, no detour.
This post is a short, very practical walkthrough of the mental procedure. It is the same logic a library uses under the hood for small inputs, written so you can run it on the back of a napkin.
Photo by Jessica Lewis 🦋 thepaintedsquare on Pexels
Why this is worth carrying in your head
The "smart" answer is "use the library." That is right whenever the input could be arbitrarily large. The "obvious" cost of always reaching for a library is the friction of fishing for the right function, the context switch, and the risk of using it wrong on tiny inputs (which is rarer than you might think but still happens).
The actual cost most teams overlook is intuition. If you cannot tell whether 211 or 219 is prime without a library, you cannot quickly reason about IDs, hashes, modular arithmetic, or hand-checked test fixtures. That intuition has to come from somewhere. It is faster to spend ten minutes once than to spend three seconds every time.
The procedure in four steps
There are exactly four checks. They get applied in order. Most numbers fail one of the first three and you never reach step four.
Step 1: parity
If the last digit is even and the number is not 2, it is composite. Done.
This catches half of all candidates instantly. It is not a "trick"; it is the consequence of the fact that 10 is divisible by 2, so the last digit determines parity by itself.
Step 2: divisibility by 3
Add the digits. If the sum is divisible by 3 and the number is not 3, it is composite.
Take 471. The digits sum to 12. Twelve is divisible by 3. So 471 is composite (in fact, 471 = 3 x 157). Take 233. The digits sum to 8. Eight is not divisible by 3, so 233 might still be prime.
This works because every power of 10 leaves a remainder of 1 modulo 3, so the original number is congruent to its digit sum modulo 3. Wolfram MathWorld has stable pages on the underlying modular arithmetic if you want the derivation.
Step 3: divisibility by 5
If the last digit is 0 or 5 and the number is not 5, it is composite.
This is the same idea as step 1 but for the other factor of 10.
Step 4: trial division by small primes up to the square root
If the number has survived the first three checks, you are down to the work. You try dividing by each prime starting at 7 and going up to the square root of the number.
The square-root cutoff matters. If N = a * b and both factors were greater than the square root of N, then a * b would be greater than N, which is impossible. So every composite has at least one factor at or below its square root. You only have to check up to that bound.
For a number around 400, the square root is 20. For 1,000, it is 32. For 10,000, it is 100. Estimate it, do not compute it.
The primes you check are 7, 11, 13, 17, 19, 23, 29, 31 up to whatever bound the square root gives you. You do not have to test composites in the range, because any composite divisor would have already been caught by its prime factors.
Photo by Monstera Production on Pexels
Translating it into code
The mental procedure maps almost directly to a clean trial-division function. Here is an outline in JavaScript:
function isPrime(n) {
if (n < 2) return false;
if (n < 4) return true; // 2 and 3 are prime
if (n % 2 === 0) return false; // step 1
if (n % 3 === 0) return false; // step 2
for (let i = 5; i * i <= n; i += 6) {
if (n % i === 0) return false;
if (n % (i + 2) === 0) return false;
}
return true;
}
The i += 6 and i, i + 2 pattern is the "skip multiples of 2 and 3" optimization. Every prime greater than 3 is of the form 6k +/- 1, so you only need to test divisors at 5, 7, 11, 13, 17, 19, etc. That is exactly the small-prime list above. The loop condition i * i <= n is the square-root cutoff.
For the same approach in Python, the Python documentation covers the standard arithmetic operators and integer types you would build it on. For larger inputs where you would want Miller-Rabin, the Wikipedia article on primality tests is the right entry point.
Worked examples
Run the procedure on three numbers and see how fast it is.
Is 211 prime? Last digit 1, not even. Digit sum 4, not divisible by 3. Last digit not 0 or 5. Square root of 211 is just under 15 (since 14^2 = 196 and 15^2 = 225). Check 7, 11, 13. 211/7 = 30.1, no. 211/11 = 19.2, no. 211/13 = 16.2, no. So 211 is prime. Total time: about 20 seconds.
Is 169 prime? Last digit 9, not even. Digit sum 16, not divisible by 3. Last digit not 0 or 5. Square root is 13 exactly. Check 7, 11, 13. 169/7 = 24.1, no. 169/11 = 15.3, no. 169/13 = 13 exactly. So 169 = 13 * 13, composite. About 15 seconds.
Is 901 prime? Last digit 1, not even. Digit sum 10, not divisible by 3. Last digit not 0 or 5. Square root is about 30 (since 30^2 = 900). Check 7, 11, 13, 17, 19, 23, 29. 901/7 = 128.7, no. 901/11 = 81.9, no. 901/13 = 69.3, no. 901/17 = 53.0 exactly. So 901 = 17 * 53, composite. About a minute.
A minute is the upper end. Most numbers are over before step 3.
When to switch to a library
The mental procedure is good up to four-digit inputs and tolerable for five-digit ones. Beyond that, the prime list to test against grows fast (about 168 primes below 1,000) and trial division starts to feel like a chore.
That is the moment to switch tools. If you are writing code, use the standard library's prime utilities. If you are doing math at the desk and just want the answer, Scientific Calculator tools that do prime factorization handle anything up to nine or ten digits effortlessly. The same calculator also does base conversion and GCD/LCM, which often come up in the same line of work.
For the longer derivation of the square-root ceiling, the full list of small primes, and the full procedure with five worked examples, the companion piece How to Tell If a Number Is Prime Quickly by Hand on the EvvyTools blog covers all of it.
A note on why this matters past primality
The mental machinery you built for primality checking is the same machinery used for modular arithmetic in general: hash functions, checksums, error-detecting codes, RSA. The "is it divisible" intuition translates to "what is the residue" intuition, which translates to seeing structure in numbers you would otherwise treat as opaque.
For a relaxed visual tour of the deeper patterns, the Numberphile site has dozens of short videos on prime distribution, factoring, and the curiosities that fall out of them. For practice problems where this exact instinct is the first step, Project Euler is the canonical archive.
The takeaway is small. Carry the four-step check in your head. Use a library when the input gets big. And when it does, the EvvyTools homepage has the tools that handle the cleanup.
Top comments (0)