Core answer: A prime is a whole number > 1 divisible only by 1 and itself: 2, 3, 5, 7, 11, 13… There are exactly 25 primes under 100 and infinitely many overall (Euclid's proof). To test whether n is prime, trial-divide only up to √n — checking 97 needs just 2, 3, 5, 7 (since √97 < 10).
Why √n is enough
If n = a × b with both a, b > 1, at least one factor is ≤ √n. So finding no divisor up to √n proves primality. For 1,000,003, that is 1,000 trial divisions instead of a million — a 1,000× speedup from one line of math.
The Sieve of Eratosthenes (find all primes ≤ N)
- List 2..N. 2 is prime — cross out its multiples (4, 6, 8…).
- Next uncrossed number (3) is prime — cross out 6, 9, 12…
- Repeat; stop crossing when the base exceeds √N.
What remains is the complete prime list. It runs in about N log log N operations — a computer finds every prime under a billion in seconds.
| Range | Prime count | Density |
|---|---|---|
| 1–100 | 25 | 25% |
| 1–1,000 | 168 | 16.8% |
| 1–10,000 | 1,229 | 12.3% |
| 1–1,000,000 | 78,498 | 7.8% |
Primes thin out like 1/ln(n) but never vanish.
Famous prime facts
- Euclid's infinity proof (~300 BC): multiply all known primes and add 1 — the result has a prime factor not on your list. Contradiction; the list never ends.
- Twin primes: pairs like (11,13), (17,19), (59,61) — infinitely many is still unproven (bounded-gap breakthrough: Zhang 2013, gaps ≤ 70M → now ≤ 246).
- Mersenne primes: 2^p − 1; the largest known primes (current record 2^82,589,933 − 1, ~24.9 million digits, found 2018).
- RSA security: multiplying two 300-digit primes is instant; factoring the product back is practically impossible — the asymmetry that secures banking.
Common mistakes and myths
- "1 is prime" — no; primes are > 1 by definition, or unique factorization (12 = 2²×3) breaks.
- "All primes are odd" — 2 is the only even prime, and the only consecutive pair (2, 3).
- Testing divisors beyond √n — wasted work; if no factor ≤ √n exists, none exists at all.
- "There's a formula for primes" — no useful one exists; polynomial n² + n + 41 gives primes for n = 0–39 then fails at 40.
- "Big primes are rare enough to run out" — at 10²⁰⁰ there are still ~1 in 460 numbers prime; crypto will never exhaust them.