Proving a Million Is Prime Takes a Thousand Divisions, Not a Million
Published 11/16/2026 · 3 min read · Everyday calculators
Lena Hoffmann — Science & education writer at OneKitly
Mathematics · Physics
Checked against 2 sources
To test whether a number has a factor, you never have to look past its square root. If a number splits into two factors, one of them is at or below the square root and the other at or above it, so finding nothing small means there is nothing at all. Checking 1 000 003 therefore needs trial divisions only up to 1000, and it survives every one of them: it is prime. Its neighbour 1 000 001 falls quickly, because 101 divides it exactly, leaving 9901. The square root is what turns an impossible search into an afternoon's work, and it is the first thing anyone writing a primality test discovers.
1 000 003 is prime and the proof stops at 1000, its square root. 1 000 001 is not, and the search ends at the third try: 101 divides it.
Only the primes need trying
Dividing by 4 is wasted effort if 2 already failed, so the list of candidates is not the thousand numbers below the square root but the 168 primes among them. That alone cuts the work by six, and skipping even numbers and multiples of three catches most of the rest almost for free. The classic implementation checks 2, then 3, then every number of the form six-either-side-of-a-multiple-of-six, which covers every possible prime and tests only a third of the integers.
Why the trick stops helping
Halving the number of digits sounds like a lot until the number is long. The square root of a 600-digit number still has 300 digits, so trial division on the keys used by modern cryptography would need more operations than there are atoms in the observable universe. Real primality testing therefore abandons division entirely and uses probabilistic tests that give a wrong answer with a probability that can be pushed below any threshold you name. Those tests prove a number is composite far more easily than they exhibit a factor, which is exactly the asymmetry the security rests on.
| Number | Divisions to try | Result |
|---|---|---|
| 1 000 001 | 3 before it fails | 101 × 9901 |
| 1 000 003 | 168 primes up to 1000 | Prime |
| A 600-digit number | More than atoms in the universe | Unusable |
Frequently asked questions
- Why is 1 not prime?
- By decision, to keep factorisation unique. If 1 counted, then 12 could be written as 2×2×3, or 1×2×2×3, or 1×1×2×2×3, and the statement that every number has exactly one prime factorisation would need an exception clause. Nineteenth-century tables did list 1 as prime, and the convention changed because every theorem was cleaner without it. Definitions in mathematics are chosen for consequences rather than discovered, and this is the clearest small example.
- How do I test a number by hand?
- Take the square root, round up, and divide by every prime up to it. For anything under ten thousand that is at most 25 divisions, most of which are dismissed instantly: even numbers fail on 2, digit sums divisible by three fail on 3, anything ending in 0 or 5 fails on 5. What survives to be tested seriously is a short list. Above a million the method becomes tedious rather than difficult, which is exactly the moment to hand it to a machine.
Articles you may find interesting
All guides →Related tools
Sources
Spotted a mistake in this article?