Great Algorithms: The Sieve of Eratosthenes

I am a huge fan of algorithms that were developed hundreds of years ago. Some of my favorites are Euclid’s algorithm, the Fibonacci Sequence, and the subject of this blog post: The Sieve of Eratosthenes.

Look at the big brain on Eratosthenes

Look at the big brain on Eratosthenes

Eratosthenes (Air-uh-tahs-thin-eeze), was one of those towering intellect types of ancient Greece. His modest achievements include inventing geography, running the library of Alexandria, and being the first to measure the circumference of the Earth (which is a great story, by the way). The sieve is actually one of his lesser known accomplishments, but it’s pretty cool nonetheless.

So, what is it? Well, the Sieve of Eratosthenes is one of the first prime number generators. It is so named because it subjects each integer to a “sieve” of primes, and if the integer makes it through without dividing evenly, it is added to the sieve as a new prime. The sieve keeps expanding as new primes enter the hallowed halls.

One interesting aspect of this is the algorithm uses its own result to power its next iteration. It’s an early example of a feedback loop.

Here’s an example of what it looks like:

Here’s an implementation in C++:

std::vector<int> SieveOfEratosthenes(int num_primes) {
  std::vector<int> sieve;
  // sieve starts with '2' already in it.
  sieve.push_back(2);
  // start our test value at the next number.
  int possible_prime = 3;
  while (sieve.size() < num_primes) {
    // we assume it’s prime, our sieve will disprove its primacy
    bool is_prime = true;
    for (auto& p : sieve) {
      // test if our number divides evenly by any prime in the sieve
      if (possible_prime % p == 0) {
        // if anything divides evenly, this number is not prime
        is_prime = false;
        break;
      }
    }
    // if we could not find an even division, that means the number is prime
    if (is_prime) {
      // add the new prime to our sieve
      sieve.push_back(possible_prime);
    }
    possible_prime += 2; // prime numbers are never even.
  }
  return sieve;
}

I find this algorithm beautiful. It’s easy to read and it accomplishes a powerful task in an elegant and simple way, but I think the sieve really shines in a functional language. This is probably because of my own personal opinions on what makes code beautiful, but I think certain objective aspects of the problem make it easier to describe in a functional language. For instance, the “infinite stream” nature, the feedback loop, and the list comprehension.

As an example, here is a solution in Scala (one of my personal favorite languages):

def sieveOfEratosthenes(s: Stream[Int]): Stream[Int] = Stream.cons(s.head, sieveOfEratosthenes(s.tail.filter(_ % s.head != 0)))
val primes = sieveOfEratosthenes(Stream.cons(2, Stream.from(3, 2)))

I love this code for many reasons. The most obvious reason is its conciseness. What took about 20 lines in C++ took us 2 lines in Scala. And it’s not the sort of conciseness that obscures the meaning of the code. If you’re familiar with Scala or other functional languages, this code is easily readable.

The main reason I love the code, though, is because it simply describes what a sieve is. That is, any number in the sieve can be described as itself followed by all subsequent numbers which can’t be divided evenly by itself. If you read the first line, you’ll see that that’s exactly what it’s saying. And the second line is simply saying that primes are a sieve of all numbers starting with 2, then 3, then all odd numbers. It’s amazing to me how a description of a sieve is also an implementation of a sieve!

Eratosthenes would be proud :-)

Jon Bedard