What Are Prime Numbers?
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. They are the atoms of arithmetic — every integer can be built by multiplying primes together. This guide covers the definition, how to test for primality, the classic sieve algorithm, prime factorisation, and real-world uses.
Definition
A natural number p > 1 is prime if and only if it has no positive divisors other than 1 and p. A number greater than 1 that is not prime is called composite. The number 1 is neither prime nor composite — it is a unit.
| Number | Prime? | Reason |
|---|---|---|
| 1 | No (unit) | Only one divisor: 1 |
| 2 | Yes | Divisors: 1, 2 only |
| 3 | Yes | Divisors: 1, 3 only |
| 4 | No | Divisors: 1, 2, 4 |
| 17 | Yes | Divisors: 1, 17 only |
| 25 | No | Divisors: 1, 5, 25 |
Trial Division — Basic Primality Test
The simplest way to test whether n is prime is trial division: try every integer d from 2 up to √n. If any d divides n evenly, n is composite. If none do, n is prime. The √n bound works because if n = a × b and both a and b are greater than √n, their product would exceed n.
Example: test whether 97 is prime. We only need to check divisors up to √97 ≈ 9.8, so we test 2, 3, 4, 5, 6, 7, 8, 9. None divide 97 evenly, so 97 is prime.
The Sieve of Eratosthenes
When you need all primes up to a limit N, the Sieve of Eratosthenes is far more efficient than testing each number individually. The sieve eliminates composites in bulk by marking multiples of each prime.
- Create a boolean array marked[0..N], initially all true.
- Set marked[0] = marked[1] = false (neither is prime).
- For each p from 2 to √N: if marked[p] is true, mark marked[p²], marked[p²+p], marked[p²+2p], … as false.
- After the loop, every index i where marked[i] is true is a prime.
Worked Example — Sieve up to 30
Start: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
- p = 2: cross out 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
- p = 3: cross out 9, 15, 21, 27
- p = 5: cross out 25
- √30 ≈ 5.5, stop here
Surviving numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — all primes up to 30.
Prime Factorisation
The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written as a unique product of primes (up to the order of the factors). This is called the prime factorisation.
To factorise n: divide by the smallest prime that divides it, then repeat on the quotient until the quotient itself is prime.
Why Prime Numbers Matter
- RSA encryption — securing internet traffic — relies on the fact that multiplying two large primes is fast, but factoring the product back into its primes is computationally infeasible.
- Hash tables and random number generators use prime-sized structures to reduce collisions.
- The distribution of primes (described by the Prime Number Theorem) is a central topic in analytic number theory.
- The Riemann Hypothesis — one of the Millennium Prize Problems — is directly about the distribution of prime numbers.
- Prime Number Finder Calculator — Check if a number is prime or list primes in a range
- Prime Number Formula — Trial division, sieve complexity, and algorithm details
Frequently Asked Questions
Are there infinitely many prime numbers?
Yes. Euclid proved this around 300 BC with a simple proof by contradiction: assume a finite list of all primes p₁, p₂, …, pₙ. The number (p₁ × p₂ × … × pₙ) + 1 is not divisible by any prime in the list, so either it is prime itself or has a prime factor not in the list — contradiction.
What is the smallest prime number?
2. It is also the only even prime number, since all larger even numbers are divisible by 2.
What is a twin prime?
Twin primes are pairs of primes that differ by 2, such as (3, 5), (11, 13), (17, 19), (29, 31). The Twin Prime Conjecture — that there are infinitely many such pairs — remains unproven.
How does Miller-Rabin testing work?
Miller-Rabin is a probabilistic primality test based on properties of modular arithmetic. For each 'witness' a, it checks whether a certain equation holds mod n. If any witness fails the test, n is definitely composite. With a fixed set of small witnesses (2, 3, 5, 7, 11, 13, 17, 19, 23), the test is deterministic for all n < 3.3 × 10²⁴.
What is the largest known prime?
As of 2024, the largest known prime is 2¹³⁶,²⁷⁹,⁸⁴¹ − 1, a Mersenne prime with over 41 million digits, discovered in October 2024.