They consider me to have sharp and penetrating vision
because I see them through the mesh of a sieve.
~Kahlil Gibran

I know that last time I promised to talk more about quantum mechanics. Unfortunately, finals hit me with all the force of a great typhoon; I don’t feel like I have the time to write an article on quantum I’d be happy with. So here’s some filler on prime numbers. Our regular programming returns next week.

A prime number is a counting number that is greater than one and only divisible by one and itself. For example, 2 is a prime number, but is not. We care about prime numbers because we can uniquely write every number as the product of some set of prime numbers (duplicates allowed). This fact is called the fundamental theorem of arithmetic and gives us a lot of information about the number in question. Thus, the more primes we know, the more we know about all numbers.

In my very first post, I proved that there are infinite prime numbers. As a natural consequence, it is impossible to solve for all prime numbers–no matter how many we solve for, there are always more prime numbers to find. However, if we restrict ourselves a little bit, it is surprisingly easy to find prime numbers. Suppose we want to find all prime numbers less than 25. We can start by writing down all numbers between 1 and 25.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Now we’re going to use the process of elimination. We’ll cross out every number that we know isn’t prime; when we’ve finished, we’ll know that the remaining numbers are prime. First, we know that 1 is specifically excluded from being prime, so let’s cross that out.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Next, let’s look at 2. 2 is divisible by 2 and 1. Thus, it’s only divisible by itself and 1–so 2 is prime. If any other number is divisible by 2, it will be divisible by more numbers than 1 and itself, so it can’t be prime. So let’s cross of all multiples of 2, or all other even numbers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Now we’re getting somewhere! The next number on our list is 3. Because we didn’t cross 3 out, we know it’s not a multiple of 2. It must be prime, then, since the only numbers before it on the list are 1 and 2. For the same reason that we crossed out the even numbers, let’s cross out all multiples of 3.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

The next number on our list is 4, but we already crossed it out, so let’s skip it. After that, we have 5. Because it’s not crossed out, we know 5 isn’t a multiple of 2 or 3, so it must be prime. Let’s cross out all multiples of 5.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

We could continue, but we’ve actually found all nine primes that are less than twenty-five. They’re just the numbers we haven’t crossed out:

2, 3, 5, 7, 11, 13, 17, 19, 23.

By filtering out the numbers we knew weren’t prime, we found all numbers that were. This process is called a number sieve, and it works just like gold panning: Take everything, but slowly remove all the stuff you don’t want, so that everything remaining is the good stuff. The particular method I used is called the Sieve of Eratosthenes, which has been known since at least 60 AD. Given any number N, you can use the sieve to find all primes less than N. When N gets really big, Eratosthenes’ method can get tedious, but computers have no trouble using it to find all prime numbers less than 10,000,000 or so. My implementation in the Julia programming language can find all prime numbers less than 2,000,000 in less than a second. (It uses a few optimizations that I won’t go into here, but if you’re curious, send a request and I’ll discuss programming optimization at some point.)

Further Reading

Where to start? There’s an unbelievable number of resources on number theory online. For more on the Sieve of Eratosthenes in particular, check out these links.

Questions? Comments? Hatemail?

As always, if you have a question, correction, comment, or insult, please don’t hesitate to tell me by email or in the comments.