O'Reilly logo

The Mathematics of Infinity: A Guide to Great Ideas, 2nd Edition by Theodore G. Faticoni

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.)

images

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:

images

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required