What is a prime number?

Some integers factor, others do not. The latter — the prime numbers — are the elementary bricks from which all the others are built.

The definition

An integer n ≥ 2 is prime if it has only two positive divisors: 1 and itself.

An integer n ≥ 2 that is not prime is called composite: it can be written n = a × b with a and b strictly between 1 and n.

primes    :  2   3   5   7   11   13   17   19   23   29   31 ...
composites:  4=2×2   6=2×3   8=2×4   9=3×3   10=2×5   12=3×4 ...

2 is the only even prime: every other even number is divisible by 2, hence composite. This is why it is sometimes called "the oddest of the primes".

Why 1 is not prime

This is no notational whim. 1 has only one divisor, whereas the definition requires exactly two. But the real reason lies elsewhere: if 1 were prime, uniqueness of factorisation would collapse.

12 = 2 × 2 × 3
   = 1 × 2 × 2 × 3
   = 1 × 1 × 2 × 2 × 3          infinitely many writings!

Excluding 1 is what allows the fundamental theorem of arithmetic to be stated without exceptions. Nineteenth-century mathematicians still counted it among the primes; they gave that up for this precise reason.

The sieve of Eratosthenes

To find all primes up to a bound, none is tested: the composites are eliminated.

1. write the integers from 2 to N
2. circle 2, then cross out all its multiples: 4, 6, 8, 10 ...
3. circle the smallest uncrossed number (3), cross out its multiples: 6, 9, 12 ...
4. repeat until past √N
5. the uncrossed numbers are the primes

 2   3   4   5   6   7   8   9  10
11  12  13  14  15  16  17  18  19  20

after elimination:

 2   3   ·   5   ·   7   ·   ·   ·
11   ·  13   ·   ·   ·  17   ·  19   ·

Eight primes below 20. This sieve, devised in the 3rd century BC, is still the most efficient way to list all primes in an interval.

Testing a single number: stop at the square root

To decide whether n is prime, there is no need to test every divisor up to n - 1.

If n is composite, it has a divisor less than or equal to √n.

Indeed, if n = a × b with a > √n and b > √n, then a × b > n: a contradiction. One of the two factors must therefore be ≤ √n.

Is 97 prime?     √97 ≈ 9.8

test 2, 3, 5, 7    (the primes ≤ 9)
   97 is odd, not divisible by 3 (9+7=16), nor by 5, nor by 7 (7×13=91, 7×14=98)

   ->  97 is PRIME

Four divisions instead of ninety-five. The gain is spectacular: for a 20-digit number it drops from 10²⁰ to 10¹⁰ tests — which, as we shall see, is still far too many.

Summary

• A prime n ≥ 2 has only two divisors: 1 and n.
• 2 is the only even prime.
• 1 is excluded to preserve the uniqueness of factorisation.
• The sieve of Eratosthenes lists all primes in a range by eliminating multiples.
• To test a single number it is enough to look for a divisor up to √n.
• There are 8 primes below 20.