Prime Number Checker: How It Works
A prime number has exactly two distinct divisors: one and itself. That simple definition underlies most of modern cryptography, which relies on the fact that multiplying two large primes is easy and reversing the multiplication is not.
Testing by trial division
To test whether n is prime, you only need to check divisors up to √n. If n has a factor larger than its square root, it must also have a corresponding factor smaller than it — so anything composite is caught by the smaller factor first.
Testing 97: √97 ≈ 9.85, so check 2, 3, 5, 7. None divides it, so 97 is prime. That is four checks instead of ninety-five.
Refining further: test 2 and 3, then only numbers of the form 6k ± 1, since every prime above 3 takes that form. This reduces the work by about two-thirds.
The first primes
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Two is the only even prime, which makes it the odd one out in every sense. One is not prime — it has only one divisor, not two, and excluding it is what makes the fundamental theorem of arithmetic work: every integer above 1 has exactly one prime factorisation. If 1 were prime, every number would have infinitely many.
How many are there
Infinitely many. Euclid's proof is about 2,300 years old and still the cleanest argument in mathematics: suppose the primes were a finite list. Multiply them all together and add one. The result leaves a remainder of one when divided by every prime on the list, so either it is prime itself or has a prime factor not on the list. Either way the list was incomplete.
They thin out as numbers grow. The prime number theorem states that the count of primes below n is approximately n ÷ ln(n) — so roughly one number in 23 is prime near 10 billion, against one in 4 below 10.
Why cryptography depends on them
Multiplying two 300-digit primes takes microseconds. Recovering those primes from the 600-digit product is, with known methods, computationally infeasible. RSA encryption rests entirely on that asymmetry.
The primes used are enormous — an RSA-2048 key uses two primes of about 1,024 bits each. Finding them relies on probabilistic tests such as Miller-Rabin, which can declare a number 'almost certainly prime' far faster than any method that proves it. The error probability is made smaller than the chance of a hardware fault, which is a reasonable place to stop.
Notable families
| Type | Definition | Example |
|---|---|---|
| Twin primes | Differ by 2 | 11 and 13, 17 and 19 |
| Mersenne primes | 2p − 1 | 3, 7, 31, 127 |
| Fermat primes | 22ⁿ + 1 | 3, 5, 17, 257, 65537 |
| Sophie Germain | p where 2p + 1 is also prime | 2, 3, 5, 11, 23 |
The largest known primes are all Mersenne primes, because an efficient specialised test exists for that form. Whether infinitely many twin primes exist remains unproven — one of the oldest open questions in mathematics.