Prime numbers.

Step 1 of 6

What a prime is

A prime number is a whole number with exactly two divisors: $1$⁠ and itself. $7$⁠ is prime; $6 = 2 \times 3$⁠ is not, and is called composite. Every composite number is a product of primes, in just one way: the primes are the building blocks of the numbers.

In the Scene the numbers from $1$⁠ to $100$⁠ are laid out in a spiral on a tray of tiles. The primes are the raised gold tiles, the composites are low and dark, and $1$⁠ is grey.

Step 2 of 6

The largest below a hundred

To check whether a number is prime, you need not try dividing it by every smaller number. It is enough to try the primes up to its square root: if $n = a \times b$⁠, one of the factors is no bigger than $\sqrt{n}$⁠.

Step 3 of 6

The sieve

Eratosthenes, in the third century BCE, found every prime up to a limit without testing any number on its own. The sieve of Eratosthenes circles $2$⁠ and crosses out all its multiples, then circles the next number not crossed out, $3$⁠, and crosses out its multiples, and so on. Every number left uncrossed is prime.

Count up to is now fixed at $400$⁠. Sieve the spiral will run the sieve: each prime crosses out its multiples in a colour of its own, from its square on, and the slate counts how many each one crossed out.

Step 4 of 6

Thinning out

The slate behind the tray counts the primes up to the limit. The further you count, the rarer they get, because a big number has more small primes that might divide it. And still they never run out: Euclid proved there are infinitely many primes.

Step 5 of 6

An eighth

At $10\,000$⁠ the tray is too large to show numbers, but the pattern stands out: the primes gather along diagonals. Nobody knows how to predict exactly where the next prime will appear.

Step 6 of 6

One easy direction

Multiplying two primes is easy, even when they are very long. Going the other way, finding the two primes from their product, is hard: no fast way is known to do it for numbers hundreds of digits long. An operation that is easy to do and hard to undo is the basis of cryptography, and the powers mod $p$⁠ from the last Lesson are another such operation.