The Sieve of Eratosthenes

A prime number is any positive integer that is only divisible by one and itself. Primes are very important across disciplines and especially in encryption and computer science. One of the reasons primes are so important is because it is very difficult to easily determine whether a number is prime or not. Moreover, what happens when you want to find, say, all the prime numbers below some $N$, say, $100$?

The Naive Approach

For each number, $n$, between $2$ and $100$, our algorithm will check for primality, returning “not a prime” if it finds a factor and “prime” if it does not. Let's assume that all of the numbers we are testing start out as prime. We'll change this if it turns out the numbers are composite. When we check our number, $n$, we will see if it is divisible by any other number, starting with $2$, then $3$, until we reach our $n$. The number we're currently checking when we run our algorithm will be outlined in black, and its possible factors will be outlined in orange.

The Naive Approach, Slightly Modified

This was a pretty inefficient way of figuring out primality. We can do better! Based off of our earlier algorithm we could see that a lot of time was wasted when we were checking a number that turned out to be prime. We can shorten this amount by instead only checking up until half of our number (because there can't be a factor greater than $\lfloor\frac{N}{2}\rfloor$). For example, when we check to see if $97$ has any factors we will only check numbers until $48$, $\lfloor\frac{97}{2}\rfloor$, instead of checking all the way to $97$ as we would have in our original algorithm.

The Naive Approach, Even Better

It still takes a long time to check for all of the factors of a prime. Let's make another change: we'll only check for factors up until the square root of our $n$ (again, because there isn't a factor greater than $\lfloor\sqrt{N}\rfloor$). Now when we check $97$ (a prime) we confirm factors until $9$, $\lfloor\sqrt{97}\rfloor$, instead of $48$, $\lfloor\frac{97}{2}\rfloor$, a difference that will only widen with larger numbers. This does require more operations in finding the square root, of course, but this will pay dividends as our $N$ gets larger (check out all these algorithms).

Introduction to the Sieve

The Sieve of Eratosthenes is useful because it's incredibly fast and easily implementable. Instead of dividing numbers we can eliminate multiples from factors, working backwards in a way. Starting with two, we know that all multiples of two cannot be prime, and so we rule these out. We repeat for three, and then when we get to four, we know that it is composite, and so we skip over it to get to five (we don't have to check for multiples of four because they are also multiples of two). Whenever we encounter a number that has been marked prime, we know that it is prime — because if it weren't, we would have eliminated it by that point.

Speeding Up the Sieve

Let's make our Sieve even faster. Instead of eliminating all multiples of each prime we hit, we can start eliminating multiples only after our prime squared. This works because for any number below our prime squared, it must have another factor that is smaller than our prime, which means it would have already been eliminated. Notice how after we hit $10$ we aren't marking any numbers composite (since $100$ is our upper limit), whereas in our original sieve we would have wasted $8$ checks.

Wheels

The next step in prime finding algorithms are wheels. You might have noticed that patterns in our grid emerged. It turns out that we can speed up our sieve by only considering certain numbers, such as only odd numbers, or only numbers that are not multiples of 2 or 3. Generalizing this concept, we get what are known as wheels. This pre-processing technique helps our algorithm because even 'passing over' a number will take time. I want to make another post visualizing these, but in the meantime, this is a great resource.

Further Reading

If this has sparked your interest in primes, awesome! There's a giant world out there. If you're interested in algorithms, not just about primes, I can't recommend Project Euler enough. It's what got me started. Also, my algorithms are constructed to show the algorithm, not as examples. As such, the algorithms used in the construction of the visualization are just representations — not true versions.

Thanks!

If there are any errata please don't hesitate to contact me at jmahabal@gmail.com. Please check out my website and other projects at www.mahabal.io.