How Prime Numbers Work

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. That one-sentence definition is all it takes to state — and yet primes are the atoms of arithmetic: every whole number above 1 is either prime or a product of primes, in exactly one way. Understanding how primes work explains why multiplication tables, factorials, and even internet encryption keep bumping into them.

1. What makes a number prime (and what doesn't)

Test a number for primality by checking its divisors. Take 12: it divides evenly by 1, 2, 3, 4, 6, and 12 — too many divisors, so it is composite. Take 7: only 1 and 7 divide it, so it is prime. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Three edge cases trip people up:

1 is not prime. It has only one divisor (itself), and the definition requires exactly two. Excluding 1 is not pedantry — it preserves the "exactly one way to factor" property. If 1 were prime, then 6 = 2 × 3 and 6 = 1 × 2 × 3 and 6 = 1 × 1 × 2 × 3 would all be different prime factorizations.

2 is the only even prime. Every other even number is divisible by 2, which immediately gives it a divisor besides 1 and itself. This makes 2 the oddest prime in the literal sense — and it means any even number above 2 can be dismissed at a glance.

Negative numbers are out of scope. Primality is defined for whole numbers greater than 1, so −7, 0, and fractions simply are not candidates.

2. How primality is actually checked: trial division

The naive method is trial division: try dividing by every candidate up to the number itself. But you can stop far earlier, because if n = a × b, then a and b cannot both exceed √n — one factor must sit below the square root and the other above. So it suffices to test divisors up to √n:

Is 97 prime? √97 ≈ 9.85, so test only 2, 3, 5, 7.
97 / 2 → no  (odd)
97 / 3 → no  (9+7 = 16, not divisible by 3)
97 / 5 → no  (doesn't end in 0 or 5)
97 / 7 → no  (7 × 13 = 91, 7 × 14 = 98 — misses 97)
→ 97 is prime

That square-root bound is why primality testing is dramatically cheaper than factoring: checking a 10-digit number takes about 100,000 trial divisions, not 10 billion. For small numbers this is all you ever need. For a quick interactive check, a prime checker runs this kind of test for you and reports the factorization when the number turns out to be composite.

3. The sieve: finding every prime below a limit

Instead of testing numbers one at a time, the Sieve of Eratosthenes (from ancient Greece, over two thousand years ago) finds all primes below a limit at once. Write out the numbers from 2 to n, then repeatedly circle the smallest uncircled number and cross out all of its multiples. Circle 2, cross out 4, 6, 8, …; circle 3, cross out 9, 15, …; circle 5 (its smaller multiples are already gone), and so on. What remains circled is exactly the prime list.

The sieve matters because it never divides anything — it exploits the structure of multiples directly. Below 100 it leaves exactly 25 primes, so among the first hundred numbers about 25% are prime (turning a count like 25/100 into a percentage is the standard part-over-whole move — see how to calculate percentages).

4. Why primes are the "atoms" of arithmetic

The fundamental theorem of arithmetic says every whole number above 1 factors into primes in exactly one way (order aside):

60 = 2 × 2 × 3 × 5   — the only prime factorization of 60
84 = 2 × 2 × 3 × 7

This is why primes earn the "atoms" nickname: composite numbers are molecules, built from prime building blocks in a fixed recipe. It is also why GCDs and LCMs (the workhorses of fraction arithmetic) are computed by comparing prime factorizations — the shared factors and the union of factors fall right out.

5. Factorials, powers, and two famous prime theorems

Primes connect to two other arithmetic workhorses: factorials and powers. A factorial n! multiplies every whole number up to n, so factorials of primes appear in a beautiful primality test called Wilson's theorem: n is prime exactly when (n − 1)! + 1 is divisible by n.

p = 7:  6! = 720, and 720 + 1 = 721 = 7 × 103   → divisible by 7 ✓ (prime)
n = 6:  5! = 120, and 120 + 1 = 121 = 11 × 11   → not divisible by 6 ✗ (composite)

Wilson's theorem is a perfect characterisation but far too slow to use for big numbers — computing 6! = 720 was easy, but the factorial explodes in size almost unimaginably fast. The practical partner is Fermat's little theorem, which uses powers instead: if p is prime and a is not a multiple of p, then a raised to the power p − 1 leaves remainder 1 when divided by p.

a = 2, p = 11:  2^10 = 1024 = 93 × 11 + 1   → remainder 1 ✓
a = 3, p = 7:   3^6  = 729  = 104 × 7 + 1   → remainder 1 ✓

Run the reverse test (a "Fermat test") on a large number with a few different bases, and any composite almost always trips an alarm. That idea, refined with extra safeguards, is how modern primality testers handle numbers with hundreds of digits — the ones used to generate cryptographic keys. Generating those keys also demands unpredictable random starting material, which is why key generation leans on cryptographically secure randomness rather than ordinary pseudorandom generators (see how pseudorandom numbers work).

6. How primes are distributed: thinner, but never gone

Primes get rarer as numbers grow, but they never run out — Euclid proved that over two thousand years ago with a lovely argument: given any finite list of primes, multiply them all together and add 1. The result leaves remainder 1 with every prime on your list, so some new prime must divide it. No finite list can be complete.

The thinning-out follows a surprisingly clean pattern called the Prime Number Theorem: a number near n is prime with probability roughly 1 / ln(n). At n = 100 that predicts about 100 / ln(100) ≈ 21.7 primes below 100 — the true count is 25, and the approximation only improves at larger scales. Near 100, primes arrive on average once every four numbers; near a trillion, roughly once every twenty-eight. Meanwhile the individual gaps swing wildly — twin primes like 11 and 13 sit right next to each other, yet gaps of any size are guaranteed to exist: for any n, the n − 1 consecutive numbers n!+2 through n!+n are all composite, because each k in that range divides n!+k evenly (try n = 5: 122, 123, 124, and 125 = 5³ are all composite). The regularity is real but lives in the averages — which, when you report averages on noisy data, is exactly where the mean-versus-median distinction from mean vs median vs mode starts to matter.

Try it yourself

Paste any number into the Prime Checker to see whether it is prime and, if not, watch it produce the full factorization. When the primes turn into factorials, the Factorial Calculator computes n! for the Wilson's-theorem checks above — try 6! and 7! and verify the divisibility by hand. And for the power side of the story, the Exponent Calculator evaluates bases raised to large exponents exactly, so you can reproduce the Fermat tests with your own choice of a and p.