A prime is a whole number greater than 1 with exactly two divisors: 1 and itself. To test one, you only need to try dividing by numbers up to its square root.
The reason is simple and worth seeing. If n has a factor a larger than √n, then n ÷ a is a factor smaller than √n — so it would already have been found. Factors come in pairs straddling the square root, and checking one side of every pair is enough. For a number near a million this cuts the work from a million divisions to about a thousand.
The square root of 1009 is about 31.8, so you only need to test primes up to 31.
| Divisor | Test | Result |
|---|---|---|
| 2 | 1009 is odd | No |
| 3 | Digit sum 1+0+0+9 = 10, not a multiple of 3 | No |
| 5 | Does not end in 0 or 5 | No |
| 7 | 7 × 144 = 1008, remainder 1 | No |
| 11 | 11 × 91 = 1001, remainder 8 | No |
| 13 | 13 × 77 = 1001, remainder 8 | No |
| 17, 19, 23, 29, 31 | All leave a remainder | No |
Eleven divisions, and 1009 is prime.
Compare its neighbour 1001, which looks equally prime and is not: 1001 = 7 × 11 × 13. That is the value of actually running the test rather than trusting intuition. Numbers that feel prime frequently are not, and the failure is usually a factor of 7, 11 or 13 that no eyeball check catches.
This looks like a convention and is actually a load-bearing decision. The fundamental theorem of arithmetic says every integer above 1 factors into primes in exactly one way. Admit 1 as a prime and that uniqueness collapses instantly: 12 becomes 2×2×3, and 1×2×2×3, and 1×1×2×2×3, endlessly. Excluding 1 keeps prime factorisation unique, which is what makes it useful. Mathematicians did once count 1 as prime; it was abandoned because the theorems were cleaner without it.
Related: 2 is the only even prime, because every other even number has 2 as a divisor. That makes 2 the exception in almost every proof about primes, and it is why efficient algorithms test 2 separately then step through odd numbers only.
Trial division is fine up to numbers with maybe fifteen digits and hopeless beyond. Cryptography needs primes of 600 digits or more, and no amount of dividing will get there.
Real systems use probabilistic tests, chiefly Miller-Rabin, which cannot prove primality but can reduce the chance of being wrong below any threshold you choose — typically far below the chance of a hardware failure. Deterministic proofs exist, such as the AKS algorithm, but they are too slow for practical key generation. So when your browser establishes an HTTPS connection, it is relying on numbers that are almost certainly prime, and that is a considered engineering choice rather than a shortcut.
RSA encryption multiplies two large primes together. Recovering them from the product is believed to be computationally infeasible, and that asymmetry — easy to multiply, hard to factor — is what secures a large share of internet traffic. Primes also determine hash table sizes, because a prime modulus distributes keys more evenly, and they show up in cicada life cycles of 13 and 17 years, where a prime period makes it hard for predators to synchronise.
A Mersenne prime — one of the form 2ᵖ − 1 — with tens of millions of digits, found by the distributed GIMPS project. Mersenne numbers dominate the record because there is a specialised test, Lucas-Lehmer, that is far faster for that particular form.
No usable one. Primes thin out predictably on average — the prime number theorem says roughly n ÷ ln(n) primes exist below n — but their individual positions have no known simple pattern. That mixture of statistical regularity and local unpredictability is why they remain interesting.
Yes, proved by Euclid around 300 BC. Multiply any finite list of primes together and add 1; the result is divisible by none of them, so either it is prime or it has a prime factor outside the list. Either way the list was incomplete.
No. The test runs in your browser and nothing you enter is transmitted or stored.
Every tool comes with a written guide, and every category is one click away.