The Mathematics of Infinity: A Guide to Great Ideas, 2nd Edition

Chapter 8

Prime Numbers

8.1 Prime Number Generators

Euclid's Theorem on Prime Numbers 7.5.2 proves that there are infinitely many primes. The next step then would be to decide where these primes are, and to discover how we could locate them amongst the well-ordered natural numbers. The pursuit of prime numbers goes back to the Greeks and is currently a source of Mathematical investigation and inspiration. We will discuss the two ends of this time line.

The Greeks had a clever way of finding the prime numbers less than some fixed number. They called it The Sieve. Basically, if you wanted to find all of the prime numbers less than a given number, let us say 60, you would first write down all of the numbers less than 60 starting with 2. (Leave 1 out because 1 is not a prime. Remember, a prime is a number p > 1 that is divisible only by 1 and itself. We exclude 1.)

All numbers divisible by 2 are excluded from our search for prime numbers so we start with 2, and move every other space, marking these numbers out as we go. We mark them out because they are divisible by 2. You stop when you reach the end of your Sieve. Observe:

Instead of striking the numbers out, we have deleted them from The Sieve. You can just strike them out with the slash /. The numbers that remain are not divisible ...