Benchmarking the Sieve of Eratosthenes

Friday. August 19, 2016 - 4 mins

Advanced concepts in computer science can sometimes be difficult to understand and difficult to execute. A great example of this is tail recurison in functional programming. The conept is easy to explain, and the notion of it running in constant stack space is easy to accept. However building programs and algorithms to be tail recursive can be a difficult task that isn’t very easy to teach. In a similar fashion explaining Floydd Warshall’s, in my opinion, is much harder than writing the simple program that implements it.

Learning the Sieve or Eratosthenes, an anchient and intuitive algorithm that generates prime numbers, reminded me of my first time learning about summing up numbers with for-loops in an intro Java class in high school. I felt this extreme sense of confidence and comfort with programming that began fading away after my first college lab assignment in C. The SOE just clicks in a way not many “advanced” concepts do in CS. (Yes I’m abbreviating Sieve of Eratosthenes to save 21 characters you’re welcome).

Naive Algorithm to Test for Primes

Testing for a prime number is tricky; here’s a simple slow method to start with:

Given the number x if any prime integer from 2 to sqaureroot(X) evenly divides n it's NOT prime.

This is reallllly slow. If your number is massive this method gets even worse. Regardless it’s probably a great intro to programming homework problem (hint hint CS101 profs) but in the business of primes we’d need something faster. Enter SOE…

The Sieve

The Sieve of Eratosthenes was developed by a Greek mathematicions somewhere around 240ish BC.

I was actually taught the sieve in a course preparing students for programming competitions where we were learning methods of Prime number generation. My love for prime numbers is non-existent, but for some odd reason I found this singular algorithm infuriatingly beautiful. Sure, it doesn’t have the overwhelming existential impacts of max flows and single shortest paths but something about the simple and intuitive nature of the SOE differentiated it from the likes of every other algorithm in this class. I found myself revisiting the algorithm two weeks later in a parallel computing course attempting to translate my java to c code and running it through OpenMP for a lab.

---

The Acutal Algorithm

The goal is to create a list of prime numbers that we can reference at constant time, ideally we can generate this list more quickly than the naïve approach

Here’s the algorithm:

1. Generate a list of integers from 2 to some limit (for our purposes let's use 21)

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

2. Since the first number of this list is 2, cross out every 2nd number on the list after 2

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

3. The next number is 3 so same idea, cross out ever 3rd number on the list after 3

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

4. 5 is the next number, however no multiples of 5 remain to be crossed out
5. We continue until there are no more numbers left to count off of and there's your list of primes (which is right now) and what we are left with is our list of primes

2 3 5 7 11 13 17 19

Simple right?

YES! I think that’s the beauty of it. I’d like to take this simple concept and see how far I can attempt to speed it up and benchmark it.

Watch this GIF that illustrates the algorithm perfectly (thanks Wikipedia) reload the page if it’s finished.

And that’s the SOE. There are faster variations (see Euler’s Sieve and this paper). But this algorithm is relatively easy to explain and understand.