How to Check if a Number Is Prime Without Testing Everything

Deciding whether a small number is prime takes seconds. Numbers in the thousands need a shortcut to stay quick, and the ones with hundreds of digits sitting behind your bank's encryption are hard enough that the whole system leans on it.

The square root shortcut

You never need to test divisors past the square root. If a number splits into a times b, one of those factors has to sit at or below the square root, because otherwise their product would overshoot. So finding no factor below the square root proves there is none above it either.

Worked through

The square root of 97 is 9.85, so the only primes worth trying are 2, 3, 5 and 7. None divide it, and that is the entire proof. The square root of 391 is 19.8, so you work up through 2, 3, 5, 7, 11, 13 and then 17, where it gives way: 391 divided by 17 is 23. Testing every number up to 390 would have taken twenty times as long for the same answer.

Divisibility tests worth memorising

Even numbers above 2 are out immediately. If the digits add to a multiple of 3, so is the number. Take 1,001: the digits add to 2, so 3 is not a factor, but 7 is, and 1,001 is 7 x 11 x 13. Anything ending in 0 or 5 divides by 5. For 11, alternately add and subtract the digits and see whether you land on 0 or a multiple of 11.

Where prime checking is actually used

Simplifying fractions is the everyday case. If the numerator is prime and does not divide the denominator, the fraction is already in its lowest terms and you can stop. Prime factorisation also drives lowest common denominators, gear ratios and anything involving repeating cycles.

The serious use is cryptography. Multiplying two large primes together is instant, while splitting the product back into its factors is not, and that asymmetry is what protects an encrypted connection. The primes involved run to hundreds of digits, which is why real systems use probabilistic tests rather than dividing by everything up to the square root.

Using the prime number checker

Type the number into the single input field and read the verdict. A good checker does two things beyond a yes or no. It shows the first factor it found, which is far more useful than a bare "composite", and it lists the full prime factorisation. Enter 391 and you should get 17 x 23 rather than just a refusal.

Numbers running to a dozen or so digits come back instantly. Past that, browser-based tools slow noticeably, because trial division scales with the square root of the number rather than the number itself. If your real task is reducing a fraction, our guide to simplifying fractions covers the shortcut, and primes are also the tidy way to reduce a surd, which the square root calculator guide walks through.

Common questions

Is 1 a prime number? No. It has only one divisor, and a prime needs exactly two. The deeper reason is that every number has one unique prime factorisation, and if 1 counted you could pad any factorisation with as many 1s as you liked.

Is 2 really prime? Yes, and it is the only even one. Every other even number has 2 as a factor. That is exactly why checking for evenness is such a good opening move.

What is the largest prime number? There isn't one. Euclid proved more than two thousand years ago that the primes never run out. There is a largest currently known prime, and it changes every few years, but the supply itself is infinite.

How do I factor a large number quickly? Strip out the small primes first. Halve it until it is odd, then try 3, then 5, then work upwards. Most composite numbers give up a small factor almost immediately. The stubborn ones are usually the product of two primes of similar size, which is precisely the case cryptography relies on.